문제
땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.
예를 들면,
| 1 | 2 | 3 | 5 |
| 5 | 6 | 7 | 8 |
| 4 | 3 | 2 | 1 |
로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.
마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.
제한사항
- 행의 개수 N : 100,000 이하의 자연수
- 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
- 점수 : 100 이하의 자연수
문제 해결
한 행씩 마다 같은 열을 연속해서 밟을 수 없기 때문에 내려온 열의 최댓값은 내려오기 전 행의 다른 인덱스의 값과 내려온 열의 인덱스를 더해 최댓값이 된다.
내려간 행의 값을 메모해놓기 위해 DP 2차원 배열을 선언한다.
입력 예제를 보면, 1,2,3,5행을 i-1행이라하고 5,6,7,8 내려갈 행(현재 행)을 i행이라하자.
그렇다면 i행의 첫번째 인덱스가 될 수 있는 최댓값은 i-1행의 첫번째 인덱스를 제외한 값과 i행의 첫번째 인덱스의 값을 더한 값중 최댓값이다. 따라서 구한 최댓값을 dp배열의 i행 첫번째 인덱스에 넣어주면 된다. 이러한 작업을 나머지 인덱스에 반복하고, land의 사이즈만큼 반복해준 후 마지막열의 최댓값을 뽑아오면 문제가 해결된다.
C++ 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<vector<int>> land){
int answer = 0;
int dp[land.size()][4];
int idx = land.size()-1;
for(int i=0; i<4; i++){
dp[0][i] = land[0][i];
}
for(int i=1; i<land.size(); i++){
for(int j=0; j<4; j++){
int max_result = 0;
for(int k=0; k<4; k++){
if(j != k){
max_result = max(max_result, land[i][j] + dp[i-1][k]);
}
}
dp[i][j] = max_result;
}
}
answer = max(max(dp[idx][0],dp[idx][1]), max(dp[idx][2],dp[idx][3]));
return answer;
}