[프로그래머스/Lv2] 땅따먹기

 

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

프로그래머스

 

 

처음에는 백트래킹으로 풀려고 했는데 생각보다 잘 안돼서 다시 생각해봤다.

우선, 같은 열을 포함하면 안된다. 아래 행으로 내려가면서 값을 더해야 하는데 그러면 맨 마지막 행에 값이 모이게 되는 것 아닌가?

그러면 이렇게 해보자. 1행은 0행의 다른 열 중 가장 큰 값을 더해주자.

이런 식으로 쭉 0열부터 3열까지 계산을 해주면 마지막 행의 열들을 모두 비교해서 가장 큰 값을 출력하면 된다!

 

 

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

int solution(vector<vector<int> > land){
    int answer = 0;
    for(int i=0; i<land.size()-1; i++){
        land[i+1][0] += max(max(land[i][1], land[i][2]), land[i][3]); //같은 열 제외하고
        land[i+1][1] += max(max(land[i][0], land[i][2]), land[i][3]);
        land[i+1][2] += max(max(land[i][0], land[i][1]), land[i][3]);
        land[i+1][3] += max(max(land[i][0], land[i][1]), land[i][2]);
    }
    answer = max(land[land.size()-1][0], max(land[land.size()-1][1], max(land[land.size()-1][2], land[land.size()-1][3])));
    return answer;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cout << solution({{1,2,3,5},{5,6,7,8},{4,3,2,1}}) << '\n'; //16
    return 0;
}