[프로그래머스] 42897. 도둑질

문제 링크

[프로그래머스] 42897. 도둑질

풀이 과정

위와 같은 원형의 배치에서 문제의 조건에 따라 인접한 두 집을 선택하지 못합니다. 따라서 아래와 같이 두 가지 경우로 나눌 수 있습니다.

1. 첫 번째 집을 선택하면, 마지막 집은 선택하지 못합니다.

2. 첫 번째 집을 선택하지 않으면, 마지막 집은 선택할 수 있습니다.

d 배열 각 요소를 i 번째 집에 도착했을 때까지 모은 돈의 최대값 으로 정의합니다. 인접한 집은 선택하지 못하므로 다음과 같은 점화식을 도출할 수 있습니다.

한 집을 건너 뛴 집까지 모은 돈의 최대값 + 현재 위치에서의 돈 과 현재 위치에서의 돈은 포기하되 바로 이전 집까지 모은 돈의 최대값 을 비교하여 더 큰 값을 해당 인덱스의 배열 요소에 저장합니다.

d[i] = Math.max(d[i - 2] + money[i], d[i - 1])

코드

public class Main {
    public static int solution(int[] money) {
        int answer = 0;

        int[] dp1 = new int[money.length];
        int[] dp2 = new int[money.length];

        dp1[0] = money[0];
        dp1[1] = Math.max(money[0], money[1]);

        for (int i = 2; i < money.length - 1; i++) {
            dp1[i] = Math.max(dp1[i - 2] + money[i], dp1[i - 1]);
        }

        dp2[1] = money[1];
        dp2[2] = Math.max(money[1], money[2]);

        for (int i = 2; i < money.length; i++) {
            dp2[i] = Math.max(dp2[i - 2] + money[i], dp2[i - 1]);
        }

        for (int i = 0; i < money.length; i++) {
            answer = Math.max(answer, dp1[i]);
            answer = Math.max(answer, dp2[i]);
        }

        System.out.println(answer);

        return answer;
    }

    public static void main(String[] args) {
        int[] money = {1, 2, 3, 1};
//        int[] money = {1, 2, 3, 3, 2, 1};
//        int[] money = {1, 2, 3, 1};
//        int[] money = {1, 2, 3, 3, 2, 1, 1};
//        int[] money = {2, 1, 3, 4, 1};

        solution(money);
    }
}