프로그래머스 - 땅따먹기 [C++]

 이 문제는 프로그래머스 level 2에 있는 문제이다. 이 문제를 처음에는 그리디한 방식으로 풀었지만, 오답이 나왔다. 결국 해답을 찾지 못해 검색을 통해 풀이를 확인했고, 다이나믹 프로그래밍과 비슷한 방식으로 풀 수 있다는 사실을 발견했다.

 

 

 내가 아쉬웠던 것은 다이나믹 프로그래밍과 같은 방식을 생각하긴 했지만, dp 배열에 무조건 답이 들어가야 한다는 생각에 빠져 해답을 찾지 못한 것이다. 코드를 보면 이전 행에서 최댓값을 더해주고, 같은 행일 때만 두번째로 큰 값을 더해주는데, 이 방식이 다이나믹 프로그래밍에서 메모이제이션과 비슷하다고 느꼈다. dp 배열에 무조건 정답이 들어가는 게 아니라 어떤 값이든 답을 찾을 수 있는 방식이라면 들어갈 수 있다는 생각을 꼭 해야겠다.

 

 

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

using namespace std;

bool compare(pair<int, int>& a, pair<int, int>& b) {
    return a.first < b.first;
}

int solution(vector<vector<int> > land) {
    int answer = 0;

    // base case
    if (land.size() == 1) {
        for (int l : land[0]) {
            answer = max(answer, l);
        }
        return answer;
    }
    
    for (int row = 1; row < land.size(); row++) {
        vector<pair<int, int>> last;
        
        for (int i = 0; i < 4; i++) {
            last.push_back({land[row - 1][i], i});
        }
        
        sort(last.begin(), last.end(), compare);
        
        for (int i = 0; i < 4; i++) {
            if (last[3].second != i) {
                land[row][i] += last[3].first;
            }
            else {
                land[row][i] += last[2].first;
            }
        }
    }
    
    for (int i = 0; i < 4; i++) {
        answer = max(answer, land[land.size() - 1][i]);
    }
    
    return answer;
}