[Programmers] 땅따먹기

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

프로그래머스

문제 설명

DP 문제이다. 처음에 완전 탐색으로 재귀를 활용하여 풀었떠니 모든 케이스에서 시간 초과가 발생했다. 이를 DP를 활용하여 해결하였다.

DP

class Solution {
    public int solution(int[][] land) {
        int answer = 0;
        int[][] dp = new int[land.length][land[0].length];
        
        for (int col = 0; col < land[0].length; col++) {
            dp[0][col] = land[0][col];
        }
        
        for (int row = 1; row < land.length; row++) {
            for (int col = 0; col < land[0].length; col++) {
                for (int prevCol = 0; prevCol < land[0].length; prevCol++) {
                    if (col != prevCol) {
                        dp[row][col] = Math.max(dp[row][col], dp[row - 1][prevCol] + land[row][col]);
                    }
                }
            }
        }
        
        for (int col = 0; col < land[0].length; col++) {
            answer = Math.max(answer, dp[land.length - 1][col]);
        }
        
        return answer;
    }
}

재귀 (시간 초과)

class Solution {
    private int answer;
    
    int solution(int[][] land) {
        for (int col = 0; col < 4; col++) {
            recur(land, 0, col, 0);
        }
        
        return answer;
    }
    
    private void recur(int[][] land, int row, int prevCol, int sum) {
        if (row == land.length) {
            answer = Math.max(answer, sum);
            return;
        }
        
        for (int col = 0; col < 4; col++) {
            if (col != prevCol) {
                recur(land, row + 1, col, sum + land[row][col]);
            }
        }
    }
}