LV2 땅따먹기 (Java)

 

---

 

문제

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

프로그래머스

풀이

단순한(?) dp(?)문제다.

 

위에서 아래로 내려오고, 같은 열의 값은 밞을 수 없다는 조건을 생각해서 dp 2차원 배열을 갱신해주면 된다.

 

dp배열의 값은 "현재 칸에 올 경우 가장 큰 값" 을 정의한다.

 

따라서 점화식은 dp[행][열] = (land[행][열]) + dp(이전 행 중 가장 큰 값) 

 

위처럼 구성되고, dp(이전 행 중 가장 큰 값)  <= 여기서 같은 열은 제외해주면 된다.

 

코드가 이해가 훨씬 쉬울거라고 생각한다.

 

코드

class Solution {
    int solution(int[][] land) {
        int answer = 0;
        int r = land.length;
        
        // initialize
        int d[][] = new int[r][4];
        for(int i=0; i<4; i++) d[0][i] = land[0][i];
        
        for(int i=1; i<r; i++){
            for(int j=0; j<4; j++){
                if(j==0) d[i][j] = land[i][j] + Math.max(Math.max(d[i-1][1], d[i-1][2]),d[i-1][3]);
                if(j==1) d[i][j] = land[i][j] + Math.max(Math.max(d[i-1][0], d[i-1][2]),d[i-1][3]);
                if(j==2) d[i][j] = land[i][j] + Math.max(Math.max(d[i-1][1], d[i-1][0]),d[i-1][3]);                
                if(j==3) d[i][j] = land[i][j] + Math.max(Math.max(d[i-1][1], d[i-1][2]),d[i-1][0]);      
            }
        }
        
        for(int i=0; i<4; i++) answer = Math.max(answer, d[r-1][i]);

        return answer;
    }
}

 

후기