프로그래머스 땅따먹기 in Java

문제

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(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 배열에 합을 저장해주었고 최종적으로 dp 배열의 가장 마지막 값을 리턴해주었다. 지금까지의 알고리즘 코드는 아래와 같다.

public static int solution(int[][] land) {
       int[] dp = new int[land.length];

       for(int i=0; i<4; i++){
           dp[0] = land[0][i];
           for(int j=1; j<land.length; j++){
              int curr = dp[j-1] + maxWithout(i, land[j]);
              dp[j] = Math.max(dp[j], curr);
           }
       }

       System.out.println(Arrays.toString(dp));
       return dp[land.length-1];
   }

   private static int maxWithout(int idx, int[] arr){
       int max = arr[0];
       for(int i=1; i<arr.length; i++){
           if(i == idx) continue;
           if(arr[i] > max){
               max = arr[i];
           }
       }
       return max;
   }

테스트케이스를 통과하였지만 제출시 전부 실패했다. 그래서 다른 테스트케이스를 찾아보니 예외 케이스는

       int[][] c3 = {{9, 5, 2, 3}, {9, 8, 6, 7}, {8, 9, 7, 1}, {100, 9, 8, 1}}; // 125

위와 같았다. 내 알고리즘대로라면 5, 9, 9,100으로 123의 값을 뽑아내지만 사실 9, 7, 9, 100을 통해 125까지 값을 뽑아 낼 수 있었다. 세 번째 뽑기에서 9를 통해 더 높은 이득을 볼 수 있었다. 다시 생각하다가 결국 못 풀고 프로그래머스 사이트의 풀이 방법을 참고하였다.

제대로 된 접근

방법은 거꾸로 접근하는 것이었다. 나는 앞에서부터 합의 최댓값을 찾으려 했기 때문에 에러가 난 것이고 사실 뒤에서부터 앞의 값을 통해 답을 구해야 했다.

i+1의 값의 최댓값은 i의 최댓값 + i+1에서 선택할 수 있는 최댓값 이었다. dp 배열의 첫 번째 값들은 그대로 두고 두 번째 값 배열들을 가능한 첫 번째 값들을 더해놓고 이 방법을 세 번째, 두 번째, ... i번째 i-1 번째 이렇게 진행시켜가면 결국 dp 배열의 마지막에 최종 값들이 기록이 되고 그 값중 가장 큰 값을 돌려주는 것이다.
정답 코드는 아래와 같다.

import java.util.*;
class Solution {  
   public int solution(int[][] land) {
       for(int i=1; i<land.length; i++){
           land[i][0] += Math.max(Math.max(land[i-1][1], land[i-1][2]), land[i-1][3]);
           land[i][1] += Math.max(Math.max(land[i-1][0], land[i-1][2]), land[i-1][3]);
           land[i][2] += Math.max(Math.max(land[i-1][1], land[i-1][0]), land[i-1][3]);
           land[i][3] += Math.max(Math.max(land[i-1][1], land[i-1][2]), land[i-1][0]);
       }

       int[] answer = land[land.length-1];
       Arrays.sort(answer);

       return answer[answer.length-1];
   }
}

테스트케이스를 바로 통과하길래 잘 풀었다고 생각했는데 결국 풀이를 보고 제출 통과했다.