[프로그래머스] Level 2. 땅따먹기

 

https://school.programmers.co.kr/learn/courses/30/lessons/12913

프로그래머스

 

 

해결 방법

1. scores 변수를 선언한다. 3차배열이다 .  scores[i][j] 는 i행j열까지 왔을때 가능한 최대값들을 저장한다. 그런데 직전위치, 즉 i-1번째에서 몇번째열이었는지가 중요하기때문에, 차원을 한차원 늘린다. scores[i][j][0] 은 land[i-1][0] 에서부터 온 값중 최대값이다. land[i][j][1] 은 land[i-1][1] 에서 온 값중 최대값이다. 
2. 0번째 행에는 이전값이 없으므로 0<= k<4 에 모두 동일한 값을 넣어준다.
3. 이제 첫번째행부터 돌면서, 다음행의 최대값을 찾는다. addScore() 을 호출한다.
4. addScore함수는 scores[i][j][k] 값을 이용해 그 다음 행인 i+1 의 점수들을 갱신하는 함수이다.
5. 열이 총 4개이므로, 4개의 열에 대해 검사하는데 만약 j == idx라면 이번열과 다음열이 동일하다는 의미이므로, 검사하지 않고 넘어간다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<vector<int>>> scores;
vector<vector<int>> land;

void addScore(int i, int j, int k){
    int sc = scores[i][j][k];
    for(int idx = 0; idx<4; idx++){
        if(idx == j) continue;
        scores[i+1][idx][j] = max(scores[i+1][idx][j],sc+land[i+1][idx]);
    }
}

int solution(vector<vector<int> > land){
    ::land = land;
    scores.resize(land.size(), vector<vector<int>>(4,vector<int>(4,0)));//i행 j열 이전k열에서 온 maxScore;
    
    for(int i =0; i<4; i++){
        for(int k=0; k<4;k++)scores[0][i][k] = land[0][i];
    }
    
    for(int i=0; i<scores.size()-1; i++){
        for(int j=0; j<4; j++){
            for(int k=0; k<4;k++){
                addScore(i,j,k);
            }
        }
    }
    
    int answer = 0;
    int idx = scores.size()-1;
    for(int j=0; j<4;j++){
        for(int k=0;k<4;k++){
            answer = max(answer,scores[idx][j][k]);
        }
    }
    return answer;
}

 

이전에 Level 3의 <경주로건설>문제의 쉬운 버전인것같다. 그전에는 "왜 이전에 움직인 경로를 저장해야하는거지?" 라고 생각했었는데 쉬운버전으로 풀어보니 왜 저장해야하는지 알겠다.