[프로그래머스] 땅따먹기 C++ 풀이 및 해설

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

프로그래머스

 

풀이 방법

2번째 행부터 시작한다.

4개의 열을 순차적으로 방문하며

이전 행의 3개의 열(같은 열은 제외)들의 값중 제일 큰 값을 현재 행(2번째 행)의 방문중인 열에 더하면

그 행에 도착할때까지 만들 수 있는 최고점이 된다.

즉, 이전 행을 이용해 큰 점수를 찾아 현재 행에 더하면 최고점이 된다. 이 방법을 끝행까지 차근차근 최고 점수를 만들자.

 

전체 코드

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

int solution(vector<vector<int> > land)
{
    int answer = 0;
    for(int i=1; i<land.size(); i++) { // 모든 행 방문
        for(int j=0; j<4; j++) { // 모든 열 방문
            int temp = -1; // 이전 행에서의 최대값을 담자
            for(int k=0; k<4; k++) { // 이전 행의 모든 열(k) 탐색
                if(k!=j) // 이전 열 k와 현재 열j가 다르다면 최대값 비교 후 갱신
                    temp = max(temp, land[i-1][k]); // 이전 행의 최대값 temp보다 크면 갱신
            }
            land[i][j] += temp; // 이전 행의 최대 값을 현재 행과 열에 더함
        }
    }
    
    for(int i=0; i<4; i++) { // 마지막 열 값들 중 최대 값이 정답.
        answer = max(answer, land[land.size()-1][i]);
    }
    return answer;
}