21.07.06 - [PG] 땅따먹기

[suhyunsim]

문제

• 12913

핵심 아이디어

• DP로 풀이
• 뒤에서부터 앞의 값을 통해 최대 값을 구하기
• i + 1에서의 최댓값: i 최댓값 + (i + 1에서 선택할 수 있는 최댓값) => 반복해서 나올 수 있는 최종 값들 중 가장 큰 값을 return

어려운 점, 실수

• 재귀로 풀면 시간초과

풀이

package main.java.com.poogle.PG.Q12913;

import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        System.out.println(solution(new int[][]{{1, 2, 5, 5}, {5, 6, 8, 7}, {4, 3, 2, 1}}));
    }

    private static int solution(int[][] land) {
        for (int i = 1; i < land.length; i++) {
            land[i][0] += Math.max(Math.max(land[i - 1][1], land[i - 1][2]), land[i - 1][3]);
            land[i][1] += Math.max(Math.max(land[i - 1][0], land[i - 1][2]), land[i - 1][3]);
            land[i][2] += Math.max(Math.max(land[i - 1][1], land[i - 1][0]), land[i - 1][3]);
            land[i][3] += Math.max(Math.max(land[i - 1][1], land[i - 1][2]), land[i - 1][0]);
        }
        int [] answer = land[land.length - 1];
        Arrays.sort(answer);
        return answer[answer.length - 1];
    }
}