[프로그래머스/JAVA] Level 4, 도둑질

https://school.programmers.co.kr/learn/courses/30/lessons/42897

프로그래머스

---

문제 설명

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다. 각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

제한사항

 

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

입출력 예

 

---

풀이

* 문제의 조건
1) 서로 인접한 두 집을 털 수 없습니다.
2) 처음과 끝의 집은 연결되어 있습니다.

먼저 문제의 제한사항을 보면, 탐색해야 할 데이터(집)의 최대가 1,000,000개라는 것을 알 수 있습니다. 따라서 dfs, 백트래킹은 메모리 초과발생하기 때문에, DP(Dynamic Programming)로 문제를 해결해야 합니다.

DP에서 중요한 것은 '최종 목표'와 '문제를 어떻게 나눌 것인가?'입니다. 우선 문제 설명에서 나왔듯이 목표는 돈의 최댓값을 구하는 것입니다. 이제 이 문제를 어떻게 작은 문제로 나눌 수 있을까요?

저는 i번째의 집의 [돈을 포함했을 때]와 [포함하지 않았을 때]로 나누었습니다. 그렇게 i가 0인 위치부터 포함했을 때와 안 했을 때를 체크하면서 최댓값을 쌓아 올리는 방법입니다. 0부터 최댓값을 쌓고, 목표 지점에 돈을 포함할 수 있는지 여부를 판단하여 합을 구한다면 이 문제의 해가 되겠습니다. 여기서 여부를 판단하는 것은 서로 인접해 있는지입니다. 가령, 현재 집의 돈을 포함한다면, 두 칸 전에 위치한 집까지 포함시켰을 때의 최댓값에서 현재 돈과 더합니다. 반대로 포함하지 않는다면, 직전의 집까지 포함시켜 구한 최댓값을 갖고 옵니다. 그리고 둘 중 더 큰 값을 현재까지의 최댓값으로 저장합니다.

해당 방법을 노드로 표현하면, 아래 그림처럼 됩니다.

트리로 표현한 DP 과정

i가 0일 때부터 돈을 포함하는지, 안 하는지를 비교하며 값을 저장하는 것인데요. 최종적으로 dp[i] 순간에 나올 수 있는 해 중 최댓값을 저장하면 되겠습니다. 여기서 우리는 메모이제이션(memoization)을 하며 문제를 풀어야 합니다. 그렇기 때문에 작은 문제의 해를 일차원 배열에 저장할 것입니다.

위 내용을 점화식으로 정리하면 아래와 같습니다.

 

* 추가로 생각해야 할 조건

마지막으로 마을이 동그랗게 배치되었다는 것을 생각해야 합니다. 이 말인즉슨, 처음의 위치한 집을 털면 마지막 집을 털지 못하고. 반대로 처음 집을 털지 않으면, 마지막 집을 털 수 있다는 의미입니다. 따라서 상황에 따른 각각의 배열을 두 개 만들어서 해를 모두 구한 뒤, 둘 중 더 큰 값을 출력하면 되겠습니다.

---

코드

public int solution(int[] money) {
    
    int houseNum = money.length;

    // 집이 3개만 있을 경우는 한 곳만 훔칠 수 있음.
    if (houseNum == 3) return Arrays.stream(money).max().getAsInt();

    int[] dpForGetFirst = new int[houseNum];
    int[] dpForIgnoreFirst = new int[houseNum];

    // 1. 첫 집을 무조건 훔쳤을 때
    dpForGetFirst[0] = money[0];
    dpForGetFirst[1] = max(money[0], money[1]);

    // 2. 첫 집을 훔치지 않았을 때
    dpForIgnoreFirst[0] = 0;
    dpForIgnoreFirst[1] = money[1];

    int i = 2;
    for (; i < houseNum; i++) {
        dpForIgnoreFirst[i] = max(dpForIgnoreFirst[i - 2] + money[i], dpForIgnoreFirst[i - 1]);

        // 첫 집을 훔친 경우는 마지막 집을 훔치지 않기 때문에 마지막 집에서 break;
        if (i == houseNum - 1) break;
        dpForGetFirst[i] = max(dpForGetFirst[i - 2] + money[i], dpForGetFirst[i - 1]);
    }

    return max(dpForIgnoreFirst[i], dpForGetFirst[i]);
}

Dynaminc Programming TIP!
1) Bottom UP 방식 = for문
2) Top Down 방식 = 재귀 (가끔 메모리 문제 발생)