땅따먹기/C++

프로그래머스

 

풀이 방법

 

 

이 문제는 동적 계산법으로 접근하였다.

 

1	2	3	5
5	6	7	8
4	3	2	1

 

예를 들어 위의 표처럼 3행 4열의 땅이 있다고 할 때 같은 열을 연속으로 밟지 않도록 하며 그 행의 가장 큰 수를 더한다 할 때 한 칸씩 내려올 때마다 결과는 아래 표처럼 된다.

 

1	2	3	5
10	11	12	11
16	15	13	13

 

n+1 행의 i번째 칸에서의 최댓값은 표에서의 n + 1 행의 i 번째 칸의 값에 n행의 i번째 칸을 제외한 다른 칸의 값 중 가장 큰 값을 더한 값과 같다는 것을 알 수 있다. 

이를 통해 점화식을 세워보면 arr[n+1][i] += max;가 될 것이고 이를 기반으로 코드를 작성하였다.

 

 

1. 한 행에서 최대값을 찾는 함수를 작성한다.

2. i = 0부터 land.size()까지 각 행에 이전 행의 같은 열을 제외한 최대값을 더해주는 것을 반복한다.

3. 반복문이 끝난 후 land[land.size()-1]에서 최댓값을 찾아 리턴한다.

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

using namespace std;

int search_max(vector<int>& v, int idx){
    int temp = 0;
    for(int i = 0; i < 4; i++) {
        if(i == idx) continue;
        temp = max(temp, v[i]);
    }
        
    return temp;
}

int solution(vector<vector<int>> land) {
    for(int i = 0; i < land.size() - 1; i++) {
        for(int j = 0; j < 4; j++) {
            land[i+1][j] += search_max(land[i], j);
        }
    }
    
    return search_max(land[land.size() - 1], 4);
}