99클럽 코테 스터디 41일차 TIL + 도둑질 (DP)

소개

• 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
• TIL이란? 'Today I Learned'의 약자로, 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
• 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.

 

 

문제 & 키워드

• 프로그래머스 - 도둑질 (문제 링크)
• 동적 계획법(DP)

 

 

---

 

 

문제 설명

도둑이 한 마을을 털려고 계획하고 있습니다. 이 마을의 모든 집들은 원형으로 배치되어 있으며, 인접한 두 집을 동시에 털면 경보가 울리기 때문에 인접한 집들을 동시에 털 수 없습니다. 각 집에 있는 돈의 양이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 구하는 문제입니다.

 

제한사항

• 마을에 있는 집의 개수는 3개 이상 1,000,000개 이하입니다.
• money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.

 

입출력 예

money = [1, 2, 3, 1]
return = 4

 

예시 설명

주어진 예시에서 집들이 원형으로 배치되어 있으며, 인접한 집들을 동시에 털 수 없습니다. 따라서 최댓값을 얻기 위해 첫 번째 집을 털거나 두 번째 집을 털고, 마지막 집을 선택해야 합니다.

 

 

---

 

 

문제 접근

1. 문제 이해
   • 문제는 원형으로 배열된 집들 중에서 최대로 돈을 훔칠 수 있는 방법을 찾는 것입니다.
   • 인접한 집을 동시에 털 수 없으므로, 첫 번째 집을 털고 마지막 집을 털지 않는 경우와 첫 번째 집을 털지 않고 마지막 집을 털는 경우로 나누어 계산할 수 있습니다.
2. 풀이 방법
   • 두 가지 경우로 나누어 동적 계획법(DP)을 적용합니다.
   • 첫 번째 경우는 첫 번째 집을 털고 마지막 집을 털지 않는 경우, 두 번째 경우는 첫 번째 집을 털지 않고 마지막 집을 털는 경우입니다.
   • 두 경우에 대해 각각 DP 배열을 사용하여 최대값을 계산한 후, 이 두 값 중 큰 값을 반환합니다.

 

 

풀이 - Java 코드

class Solution {
    public int solution(int[] money) {
        int[] firstDp = new int[money.length];
        int[] secondDp = new int[money.length];

        if (money.length == 3) {
            int maxNum = 0;

            for (int amount : money) {
                maxNum = Math.max(amount, maxNum);
            }

            return maxNum;
        }

        for (int i = 0; i < money.length; i++) {
            firstDp[i] = money[i];
            secondDp[i] = money[i];
        }

        firstDp[1] = -1;
        firstDp[2] += firstDp[0];

        secondDp[0] = -1;

        // DP[i] = 현재 집을 털 때 최대 돈의 양 계산
        for (int i = 3; i < money.length; i++) {
            firstDp[i] += Math.max(firstDp[i - 2], firstDp[i - 3]);
            secondDp[i] += Math.max(secondDp[i - 2], secondDp[i - 3]);
        }

        int firstMax = Math.max(firstDp[firstDp.length - 2], firstDp[firstDp.length - 3]);
        int secondMax = Math.max(secondDp[secondDp.length - 1], secondDp[secondDp.length - 2]);

        return Math.max(firstMax, secondMax);
    }
}

풀이 설명

1. 초기화
   • money 배열을 기반으로 두 개의 DP 배열(firstDp와 secondDp)을 초기화합니다.
   • 첫 번째 경우 (firstDp)는 첫 번째 집을 털고, 두 번째 집을 털지 않도록 설정합니다.
   • 두 번째 경우 (secondDp)는 첫 번째 집을 털지 않도록 설정합니다.
2. DP 계산
   • 각각의 경우에 대해 DP 배열을 순회하며 최대값을 갱신합니다.
   • 두 경우 중 더 큰 값을 최종적으로 반환합니다.
3. 결과 반환
   • 두 경우 중에서 최대값을 구해 반환합니다.

 

 

---

 

 

마무리하며

이번 문제는 원형으로 배열된 집에서 최댓값을 찾는 문제로, 동적 계획법(DP)을 활용해 효율적으로 해결할 수 있었습니다.

원형 배열에서의 DP 문제는 인접한 요소들을 어떻게 처리할지에 대한 고민을 하였으며, 이 문제에서는 두 가지 경우로 나누어 계산하는 방법을 사용했습니다.