[ 프로그래머스 땅따먹기 (Lv2) ] (C++)

프로그래머스의 땅따먹기(Lv2) 문제이다.

[ 문제풀이 ]

같은 열에 존재하는 연속된 땅을 밟을 수 없을 때 구할 수 있는 최고값을 구해야 하는 문제이다.

본인은 단순 3중 for문을 통해서 각 행에서의 최고값들을 구해주었다.

먼저 사용한 핵심 변수로는 Score[][] 이라는 int형 2차원 배열이다.

Score[a][b] = c 의 의미는 "(a, b) 즉, a행 b열을 지날 때 얻을 수 있는 최고값은 c점입니다" 를 의미한다.

즉, 최종적으로는 Score[land.size()][0],[1][2][3] 이렇게 4개의 값 중에서 최고값을 찾아내면 되는 것이다.

다른 알고리즘 보다는 단순 for문으로 구했으니 코드를 보고 각 for문이 어떤 의미를 갖고 있는지 알아보자.

{
    for (int i = 0; i < 4; i++) Score[0][i] = land[0][i];
    for (int i = 1; i < land.size(); i++)
    {
        for (int j = 0; j < 4; j++)
        {
            for (int k = 0; k < 4; k++)
            {
                if (j == k) continue;
                Score[i][j] = Bigger(Score[i][j], land[i][j] + Score[i - 1][k]);
            }
        }
    }
 
    int Answer = 0;
    for (int i = 0; i < 4; i++) Answer = Bigger(Answer, Score[land.size() - 1][i]);
    return Answer;
}

먼저 line2)에서 가장 초기값을 설정해 주고 있다.

0행에서는 각 행에서의 값이 최고값이기 때문에(이전의 행이 없기 때문에) 그대로 설정해 주고 있다.

line3)에 존재하는 for문은 행을 의미한다. 즉, 0행의 값은 line2)에서 구했고, 1행부터 land.size() 행까지 반복하게 된다.

line5)에 존재하는 for문은 열을 의미한다. 즉, 우리는 Score[i][j]의 값, 다시 말해서 (i, j)를 지나게 될 때의 최댓값을

구하는데, 이 때 사용되는 열을 의미하는 j값이다.

line7)에 존재하는 for문은 이전에 들렸던 열을 의미한다. 즉, j와 k값이 같다라는 것은, 이전에 들렸던 열과 지금 현재 열이

동일하다는 것을 의미하고 이 부분은 line9)에 존재하는 조건문으로 걸러주었다.

line10)에서 보면 (i, j)를 지날 때 얻을 수 있는 최댓값을 갱신해주면서 설정해 주고 있다.

즉, (i, j)를 지날 때 얻을 수 있는 최댓값은 (i - 1, k)에서의 최댓값 + (i, j)의 값이 된다.

[ 소스코드 ]

#include<vector>
using namespace std;
 
int Score[100010][4];
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
int solution(vector<vector<int>> land)
{
    for (int i = 0; i < 4; i++) Score[0][i] = land[0][i];
    for (int i = 1; i < land.size(); i++)
    {
        for (int j = 0; j < 4; j++)
        {
            for (int k = 0; k < 4; k++)
            {
                if (j == k) continue;
                Score[i][j] = Bigger(Score[i][j], land[i][j] + Score[i - 1][k]);
            }
        }
    }
    
    int Answer = 0;
    for (int i = 0; i < 4; i++) Answer = Bigger(Answer, Score[land.size() - 1][i]);
    return Answer;
}