프로그래머스 : 땅따먹기 [C++]

문제 링크

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

 

문제 설명

1. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다.
2. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 
3. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

 

문제 입출력 예)

land	answer
[[2, 1, 3, 2], [5, 6, 7, 8], [4, 3, 2, 1]]	16

 

문제 풀이

 

위와 같은 문제는 DP로 풀어야하는 문제이다.

Dynamic Programming (동적 계획법)

DP란?

문제를 여러 개의 문제로 나누어 푸는 방법이다.
분할 정복과 비슷하며, 큰 부분을 풀어나갈 때, 앞서 메모해 놓은 결과값을 이용해서 풀이하는 프로그래밍이다.

#include <iostream>
#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(land[i][1],max(land[i][2],land[i][3]));
        land[i+1][1] += max(land[i][0],max(land[i][2],land[i][3]));
        land[i+1][2] += max(land[i][0],max(land[i][1],land[i][3]));
        land[i+1][3] += max(land[i][0],max(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;
}

 

ㅣ1ㅣ2ㅣ3ㅣ5ㅣ
ㅣ5ㅣ6ㅣ7ㅣ8ㅣ
ㅣ4ㅣ3ㅣ2ㅣ1ㅣ 
위와 같이 주어졌을 때

ㅣ1ㅣ2ㅣ3ㅣ5ㅣ
ㅣ10ㅣ11ㅣ12ㅣ11ㅣ
ㅣ16ㅣ15ㅣ13ㅣ13ㅣ
위와 같은 답이 나오기 때문에 16이 정답이다. 

리뷰

DP 동적할당법 프로그래밍 공부,,