땅따먹기

문제 정보

• 프로그래머스 Lv.2
• DP
• 문제 링크

풀이

간단한 DP 문제다.

상태 배열 dp[i][j]를 다음과 같이 정의한다.

• dp[i][j]: i번째 행의 j열에 도착했을 때의 최대 점수

다만 같은 열을 연속해서 밟을 수 없다는 조건 때문에, 이 부분에 대한 조건 검사를 해줘야 한다.

코드

class Solution {
    int solution(int[][] land) {
        int answer = 0;
        int[][] dp = new int[land.length][4];
        
        for (int i = 0; i < 4; i++) 
            dp[0][i] = land[0][i];
        
        
        for (int i = 1; i < land.length; i++) {
            for (int j = 0; j < 4; j++) { // 현재 행에서 선택한 열
                for (int k = 0; k < 4; k++) { // 이전 행에서 선택했던 열
                    if (k == j) continue; // 같은 열일 경우 스킵
                    
                    // 이전 행의 k열에서 왔을 때, 현재 행의 j열을 밟는 경우의 최대 점수
                    dp[i][j] = Math.max(dp[i][j], land[i][j] + dp[i - 1][k]);
                }
            }
        }
 
		// 마지막 행의 4개 열 중 최대값이 답
        for (int i = 0; i < 4; i++)
            answer = Math.max(answer, dp[land.length - 1][i]);
        
        return answer;
    }
}