[C++] Programmers 땅따먹기 풀이

풀이 방법

해당 문제는 동적 계획법으로 풀었지만, 동적 계획법으로 푸는 문제 중 난이도가 높은 문제는 아닙니다. 지나온 땅의 합을 저장하기 위해 땅의 크기와 동일한 2D vector를 선언합니다. programmers에서 제공하는 알고리즘 문제 풀이에서는 해당 부분을 2D array 형태로 선언헀지만, array로 필요한만큼만 선언하려면 동적할당을 사용해야하는데, 귀찮아서 vector 형태로 선언했습니다.

해당 2D vector를 A라고 할때 A[i][j]에는 land[i][j]까지 오는 방법 중 지나온 숫자의 합이 가장 큰 값을 저장합니다. 이 때 가장 큰 값을 구하는 방법은 A[i-1] 중 A[i-1][j]를 제외한 가장 큰 값과 land[i][j]를 더하는 것입니다. 코드는 아래 전체 성공 코드를 참고하시고, Programmers에서 제공하는 해설도 아래에 기재해 놓겠습니다. 

programmers.co.kr/learn/courses/18/lessons/929

알고리즘 문제 해설 - 5번 코드 풀이

전체 성공 코드

#include <iostream>
#include <vector>
using namespace std;

int solution(vector<vector<int> > land)
{
    int row = land.size();
    int column = 4;
    vector<vector<int>> dp(row, vector<int> (column, 0));

    for (int j = 0; j < column; j++) {
        dp[0][j] = land[0][j];
    }
    
    for (int i = 1; i < row; i++) {
        for (int j = 0; j < column; j++) {
            int temp = 0;
            for (int k = 0; k < column; k++) {
                if (j != k) {
                    temp = max(temp, dp[i-1][k]);
                }   
            }
            dp[i][j] = temp + land[i][j];
        }
    }
    
    int answer = 0;
    for (int i = 0; i < column; i++) {
        answer = max(answer, dp[row-1][i]);
    }
    return answer;
}

채점 결과