[99클럽 코테 스터디 13일차 TIL] 동적계획법

📖 오늘의 학습 키워드
동적계획법

오늘의 회고

문제

[도둑질]
https://school.programmers.co.kr/learn/courses/30/lessons/42897

나의 해결

class Solution {
    public int solution(int[] money) {
        int len = money.length;
        long[] dp1 = new long[len];
        long[] dp2 = new long[len];
        dp1[0] = money[0];
        dp1[1] = money[0];
        dp2[1] = money[1];
         for(int i = 2; i < len; i++) {
            dp1[i] = Math.max(dp1[i-2] + money[i], dp1[i-1]);
            dp2[i] = Math.max(dp2[i-2] + money[i], dp2[i-1]);
        }
        int answer = (int)(Math.max(dp1[len-2], dp2[len-1]));
        return answer;
    }
}

1. 모든 집들이 동그랗게 배치되어 있기 때문에 두 가지 경우가 발생한다.
   • 첫 번째 집에서 훔치면 마지막 집에서 훔칠 수 없다.
     • dp1
   • 첫 번째 집에서 훔치지 않으면 마지막 집에서 훔칠 수 있다.
     • dp2
2. i번째 집까지 도둑이 훔칠 수 있는 돈의 최댓값은 "i-1번 째 집까지의 최대값"과 "i-2번 째 집까지의 최대값과 현재 집에 있는 돈을 합한 값" 중 더 큰 값이다.
   • dp[i] = Math.max(dp[i-2] + money[i], dp[i-1])
3. dp1[len-2]과 dp2[len-1] 중 더 큰 수를 정답으로 반환한다.
   • Math.max(dp1[len-2], dp2[len-1])
   • dp1은 마지막 집을 훔칠 수 없어서 dp1[len-2]
   • dp2는 마지막 집을 훔칠 수 있어서 dp2[len-1]

새로 학습한 내용

레벨 4치고는 쉽게 느껴진 DP 문제였던 것 같다. 집들이 원형으로 배치된 것을 고려해 두 가지 경우로 나눠 풀어야 한다는 점이 다른 문제와 조금 달랐던 것 같다.