[12913] 땅따먹기

✔ 땅따먹기

[프로그래머스 12913]

문제 분석하기

주어진 행인 N이 100000이므로 방문 배열과 시간 복잡도가 O(V + E)인 DFS를 이용할 경우 시간 초과가 발생하므로

DP를 이용해 각 행의 0,1, 2, 3열에 도달하기까지 누적한 점수의 최댓값을 저장하도록 함

손으로 풀어보기

1. 점화식의 형태와 의미를 도출
   • land[i][j]는 i번째 행의 j번째 열까지의 누적된 점수의 합
2. 점화식을 구하여 각 행의 0, 1, 2, 3열에 도달하기까지의 누적된 점수의 합으로 갱신해주도록 함
   • land[i + 1][0]은 이전 열에서 0을 사용하지 않았어야 하므로 land[i][1], land[i][2], land[i][3]에서 가장 큰 값을 사용
   • land[i + 1][1]은 이전 열에서 1을 사용하지 않았어야 하므로 land[i][0], land[i][2], land[i][3]에서 가장 큰 값을 사용 
   • land[i + 1][2]은 이전 열에서 2을 사용하지 않았어야 하므로 land[i][0], land[i][1], land[i][3]에서 가장 큰 값을 사용
   • land[i + 1][3]은 이전 열에서 3을 사용하지 않았어야 하므로 land[i][0], land[i][1], land[i][2]에서 가장 큰 값을 사용
3. 최댓값을 반환

슈도코드 작성하기

land(땅따먹기 게임의 땅)
answer(마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값)
for(i -> 0부터 land의 길이 - 1까지) {
    land[i + 1][0] += Math.max(Math.max(land[i][1], land[i][2]), land[i][3])
    land[i + 1][1] += Math.max(Math.max(land[i][0], land[i][2]), land[i][3])
    land[i + 1][2] += Math.max(Math.max(land[i][0], land[i][1]), land[i][3])
    land[i + 1][3] += Math.max(Math.max(land[i][0], land[i][1]), land[i][2])
}
for(i -> 4까지) {
    answer = Math.max(answer, land[land.lengh - 1][i])
}
answer 반환

코드 구현하기

/**
 * 12913) 땅따먹기
 */
public class L010_12913 {
    // land(땅따먹기 게임의 땅)
    int solution(int[][] land) {
        // answer(마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값)
        int answer = 0;
        // 자신이 사용할 수 있는 이전 열 중 가장 큰 값으로 갱신 (DP)
        for (int i = 0; i < land.length - 1; i++) {
            land[i + 1][0] += Math.max(Math.max(land[i][1], land[i][2]), land[i][3]); // 이전 열에서 0을 사용하지 못함
            land[i + 1][1] += Math.max(Math.max(land[i][0], land[i][2]), land[i][3]); // 이전 열에서 1을 사용하지 못함
            land[i + 1][2] += Math.max(Math.max(land[i][0], land[i][1]), land[i][3]); // 이전 열에서 2를 사용하지 못함
            land[i + 1][3] += Math.max(Math.max(land[i][0], land[i][1]), land[i][2]); // 이전 열에서 3을 사용하지 못함
        }
        // 마지막 열에서 가장 큰 점수로 갱신
        for (int i = 0; i < 4; i++) {
            answer = Math.max(answer, land[land.length - 1][i]);
        }
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L010_12913 solution = new L010_12913();

        int[][] land = { { 1, 2, 3, 5 },
                { 5, 6, 7, 8 },
                { 4, 3, 2, 1 } };

        int result = solution.solution(land);

        System.out.println(result);
    }
}