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

programmers.co.kr/learn/courses/30/lessons/12913

코딩테스트 연습 - 땅따먹기

 

입력값의 범위가 100,000 이하의 자연수이기 때문에, 단순히 O(N*N) 방법으로 풀면 시간초과로 인해 문제를 해결할 수 없다. 보통 이러한 시간 초과 문제를 해결하기 위해서 DP를 사용하는 것 같다.

 

다음 행으로 이동할 때마다 각 열의 누적합을 구해주면 된다. 

 

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

 

| 1   | 2  | 3   | 5  |

| 10 | 11 | 12 | 11 |

| 16 | 15 | 13 | 13 |

 

 

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

int solution(vector<vector<int> > land)
{
    for(int i = 1; i < land.size(); i++) {
        land[i][0] += max(land[i-1][1], max(land[i-1][2], land[i-1][3]));
        land[i][1] += max(land[i-1][0], max(land[i-1][2], land[i-1][3]));
        land[i][2] += max(land[i-1][0], max(land[i-1][1], land[i-1][3]));
        land[i][3] += max(land[i-1][0], max(land[i-1][1], land[i-1][2]));
    }
    return *max_element(land[land.size() - 1].begin(), land[land.size() - 1].end());
}