프로그래머스 Lv.2) 땅따먹기

땅따먹기

코딩테스트 연습 - 땅따먹기

풀이

나를 좌절하게 만든 문제였다... 분명 DP를 활용하는 문제임을 눈치챘고 유사한 문제도 풀어냈었는데, 검색과 자동완성 기능 없이 풀어야한다는 생각이 들어서 그랬을까 못풀었다. 그래서 프로그래머스에서 제공하는 문제의 해답 영상을 봤다. 마지막 행의 4개의 x에 대해 bottom-up 방식으로 dp를 진행하는 것이었다.. 분명 이렇게 풀었던 dp문제가 있었던게 기억났다. 생각보다 간단했다..

 

로직

1. 행의 길이와 x의 개수(4)만큼 2차원 int 배열 dp를 초기화하고 마지막 행에 대해 x축 각각의 수를 저장했다.

2. 1을 통해 y의 마지막 인덱스는 저장이 되었으니, y-1부터 0까지 포문을 돌면서 바로 아래 단계의 dp와 비교해 각각의 dp를 저장했다.

 2-1. 문제의 조건에 따라, dp의 y+1값 (bottom-up 이니까 이전값)들 중 같은 열이 아닌 값 3개에 대해 최대값을 구해줬다.

 2-2. 최대값과 현재 위치의 land 값을 dp에 저장해주었다.

3. 0번째 인덱스의 4개 dp값에 대해 최대값을 구해 리턴해주었다.

 

코드

public class HopScotch_12913 {
    private static int solution(int[][] land) {
        int answer =0;
        int[][] dp = new int[land.length][4];
        for(int i=0; i<4; i++) { // initailize
            dp[land.length-1][i] = land[land.length-1][i];  // root value
        }
        // bottom-up 으로 풀이... , 문제 해설 영상 참고해서 품..
        for(int y=land.length-2; y>=0; y--) {
            for(int idx=0; idx<4; idx++) {
                for(int x =0; x<4; x++) {
                    if(x != idx) {
                        dp[y][idx] = Math.max(dp[y+1][x], dp[y][idx]);
                    }
                }
                dp[y][idx] += land[y][idx];
            }
        }
        for(int i=0; i<4; i++) {
            answer = Math.max(dp[0][i], answer);
        }
        return answer;
    }
    public static void main(String[] args) {
        int[][] land = {{1,2,3,5},{5,6,7,8},{4,3,2,1}};
        System.out.println(solution(land));
    }
}