프로그래머스 땅따먹기

문제 링크

코드 설명

처음에는 완전탐색 DFS로 접근하였지만 깊이가 최대 100000이므로 DP를 생각했어야했다.

0행부터 내려갈수록 누적값을 더해주는데 그때마다 그 상황에서의 max값을 담아준다.

n주어지는 크기부터 보고 알고리즘을 생각하는 습관을 가지자!

소스 코드

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

int solution(vector<vector<int> > land)
{
    int answer = 0;
    
    int n = land.size();
    for (int i = 1; i < n; i++) {
        land[i][0] += max(max(land[i-1][1], land[i-1][2]), land[i-1][3]);
        land[i][1] += max(max(land[i-1][0], land[i-1][2]), land[i-1][3]);
        land[i][2] += max(max(land[i-1][0], land[i-1][1]), land[i-1][3]);
        land[i][3] += max(max(land[i-1][0], land[i-1][1]), land[i-1][2]);
    }
    answer = max(max(max(land[n - 1][0], land[n - 1][1]),land[n - 1][2]),land[n-1][3]);

    cout << answer;
    return answer;
}

int main() {
    
    solution({ {1,2,3,5},{5,6,7,8},{4,3,2,1} });

    return 0;
}