[프로그래머스](Java) - 땅따먹기

문제 링크

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

문제 풀이

TestCase
[[1, 2, 3, 5], [5, 6, 7, 8], [4, 3, 2, 1]] 에 대해

[0, 0, 0, 0], [1, 2, 3, 5], [0, 0, 0, 0], [0, 0, 0, 0]

[[0, 0, 0, 0], [1, 2, 3, 5], [10, 11, 12, 11], [0, 0, 0, 0]]

[[0, 0, 0, 0], [1, 2, 3, 5], [10, 11, 12, 11], [16, 15, 13, 13]]

와 같은 과정을 통해서 결과가 도출된다.
land[0] 값을 dp[1]에 매칭해주기 위해서 dp의 length는 land.length의 +1을 해주고
dp[0]의 값들은 모두 0으로 한다.
그리고 dp[1]의 값들은 land의 첫번째행의 값들을 가진다.

두번째 부터 for문을 통해서 max값을 찾게되는데
dp[2]의 값들은 land[1]의 각 행의 값들을 기본적으로 가진다.
이는 dp[i][j] = land[i-1][j] 부분이면
여기서 같은 j가 아닌 값들 중에서 제일 큰 이전값을 찾는다.

ex)dp[2][1]은 dp[1][1]의 값에서 + 가 될수 없다.
따라서 dp[2][1]은 dp[1][0], dp[1][2], dp[1][3]의 값중에서 제일 큰값을 선택할것이다. 따라서 dp[2][1] = land[1][1] + Math.max(dp[1][0], dp[1][2], dp[1][3]) 이다.

Math.max 두 수의 비교이므로 여기서 Math.max를 2번 해주면 된다.
본인은 method로 빼서 처리했다.

그리고 마지막 행에서 가장 큰 값이 answer 가 된다.

코드

import java.util.*;

class Solution {
    int solution(int[][] land) {
        int answer = 0;

        int [][] dp = new int[land.length+1][4];
        
        dp[0][0] = 0;
        dp[0][1] = 0;
        dp[0][2] = 0;
        dp[0][3] = 0;
        
        dp[1][0] = land[1][0];
        dp[1][1] = land[1][1];
        dp[1][2] = land[1][2];
        dp[1][3] = land[1][3];
        
        int idx = -1;
        for(int i=1; i<=land.length; i++){
            dp[i][0] = land[i-1][0]+findMax(0,i,dp);
            dp[i][1] = land[i-1][1]+findMax(1,i,dp);
            dp[i][2] = land[i-1][2]+findMax(2,i,dp);
            dp[i][3] = land[i-1][3]+findMax(3,i,dp);
            
        }
        
        
        //System.out.println(Arrays.deepToString(dp));
        for(int i=0; i<4; i++){
            answer = Math.max(answer,dp[dp.length-1][i]);
        }
        return answer;
    }
    
    public static int findMax(int idx,int i, int[][] dp){
        int res =0;
        switch(idx){
            case 0:
               res = Math.max(dp[i-1][1], dp[i-1][2]);
               res = Math.max(res,dp[i-1][3]);
               break;
            case 1:
               res = Math.max(dp[i-1][0], dp[i-1][2]);
               res = Math.max(res,dp[i-1][3]);
               break;
            case 2 :
               res = Math.max(dp[i-1][0], dp[i-1][1]);
               res = Math.max(res,dp[i-1][3]);
               break;
            case 3:
               res = Math.max(dp[i-1][0], dp[i-1][1]);
               res = Math.max(res,dp[i-1][2]);
               break;
  
        }        
        return res;
    }
}