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

- 문제설명

 

 

- 풀이코드

 

#include <iostream>
#include <algorithm>
#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_element(land[n-1].begin(),land[n-1].end());
    
    return answer;
}

 

- 시간복잡도

 

O(nlogn)  -> 배열을 채워나가는 과정은 O(n)이지만 마지막에 최대값을 찾는데 O(nlogn) 이므로

 

- 남의 풀이와 비교

 

문제를 보고 가장 처음 생각난 방법은 그냥 나이브하게 모든 경우를 다해보면 되지 않을까 싶었는데 n이 10만이였다. 모든 경우를 다 해보는 경우에는 시간복잡도가 n^2 이므로 안된다는 것을 알았고 어떻게하면 될까 고민하던 찰나에 이전에 풀어봤던 정수삼각형이라는 문제가 떠올라서 DP로 쉽게 풀 수 있었다. 다른 사람들의 풀이를 봐도 시간 복잡도 때문에 내가 푼 방법과 같았다.

 

- Reference

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

https://programmers.co.kr/learn/courses/30/lessons/43105 정수삼각형