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

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

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

 

이 문제는 각 행의 원소 개수가 4개로 고정되어 있고, 행을 한 칸씩 내려갈 때 그 이전 행과 동일한 열을 선택할 수 없는 조건만 존재합니다.

 

완전 탐색으로 모든 경우를 보기 위해서는 O(3^N) 만큼의 시간 복잡도가 소요되기 때문에 제한된 시간 안에 문제를 해결할 수 없습니다. *시간 복잡도가 O(3^N)인 이유는 각 행을 내려갈 때마다 3개의 선택지가 존재하기 때문입니다.

 

따라서 이 문제는 DP를 통해 해결할 수 있는데요. DP의 정당성은 간단하게 파악할 수 있습니다.

 

'dp[i][j] = i번째 행 j열에서 얻을 수 있는 점수의 최대값'이라고 정의하면, dp[i][j]는 dp[i-1][k](k = 0, 1, 2, 3 && k != j)의 최대값에서 현재 자신의 값을 더한 값으로 정의될 수 있기 때문입니다. 즉, 어떤 지점에서의 최대값은 그 이전 지점들(부분 문제)의 최대값을 그대로 인용한다는 것입니다.

 

따라서 위에서 정의한 DP 점화식을 그대로 코드로 옮겨주기만 하면 됩니다.

 

 

[풀이 - 파이썬]

def solution(land):
    n = len(land)
    # dp[i][j] = i행 j열에서 점수의 최대값
    # dp 초기화
    dp = [[0,0,0,0]] + land
    for i in range(1, n+1):
        # 이전 행에서 같은 열을 제외한 값 중 최대값과 현재값을 더한다.
        dp[i][0] += max(dp[i-1][1], dp[i-1][2], dp[i-1][3])
        dp[i][1] += max(dp[i-1][0], dp[i-1][2], dp[i-1][3])
        dp[i][2] += max(dp[i-1][0], dp[i-1][1], dp[i-1][3])
        dp[i][3] += max(dp[i-1][0], dp[i-1][1], dp[i-1][2])
    
    return max(dp[n])
print(solution(land=[[1,2,3,5],[5,6,7,8],[4,3,2,1]]))

 

[풀이 - 자바]

package PS;

import java.util.Arrays;
import java.util.stream.Stream;

public class Programmers_EatGround {
    int solution(int[][] land) {
        int n = land.length;
        int[][] zeros = {{0,0,0,0}};
        int[][] dp = Stream.of(zeros, land).flatMap(Stream::of).toArray(int[][]::new);

        for(int i = 1; i < n+1; i++){
            dp[i][0] += findMax(dp[i-1][1], dp[i-1][2], dp[i-1][3]);
            dp[i][1] += findMax(dp[i-1][0], dp[i-1][2], dp[i-1][3]);
            dp[i][2] += findMax(dp[i-1][0], dp[i-1][1], dp[i-1][3]);
            dp[i][3] += findMax(dp[i-1][0], dp[i-1][1], dp[i-1][2]);
        }
        Arrays.sort(dp[n]);
        return dp[n][3];
    }
    static int findMax(int a, int b, int c){
        int result = Integer.MIN_VALUE;
        if (a > result) result = a;
        if (b > result) result = b;
        if (c > result) result = c;
        return result;
    }
    // 디버깅
    public static void main(String[] args) {
        Programmers_EatGround c = new Programmers_EatGround();
        int[][] test = { { 1, 2, 3, 5 }, { 5, 6, 7, 8 }, { 4, 3, 2, 1 } };
        System.out.println(c.solution(test));
    }
}