[C++] 프로그래머스 - 도둑질

🔐 프로그래머스 - 도둑질

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

🔑 풀이

이 문제는 원형의 집 배열에서 도둑이 훔칠 수 있는 최대 금액을 구하는 문제로 인접한 집을 동시에

털 수 없다는 제약을 가지고 있다. 배열이 원형으로 되어있으므로, 첫 번째 집과 마지막 집은 인접해

있으며, 둘 중 하나만 고를 수 있다. 따라서 다음의 두 가지 경우로 나눠 생각해 볼 수 있다.

• 첫 번째 집을 터는 경우 → 마지막 집을 털 수 없음

• 첫 번째 집을 털지 않는 경우 → 마지막 집을 털 수 있음

위 두 가지에 대한 점화식은 다음과 같다.

$ dp1[i] $ 를 i번째 집까지 털 수 있을 때의 최대 금액으로 두면, 점화식을 다음과 같이 세울 수 있다.

$ dp1[i] = max(dp1[i-1], dp1[i-2] + money[i]) $

• dp1[i - 1] : i번째 집을 털지 않고, 이전까지 턴 최대 금액

• dp1[i - 2] + money[i] : i번째 집을 털고, i - 2 번째 집까지 턴 최대 금액을 더한 값

이제 점화식을 두 가지 경우에 대입하면 다음과 같다.

첫 번째 집을 터는 경우

• 초기조건 : dp1[0] = money[0], dp1[1] = money[0]

두 번째 집을 터는 경우

• 초기조건 : dp2[1] = money[1]

이제 마지막으로 위의 두 가지 중 최대값을 선택해야 하며, 최종 결과는 다음과 같다.

$ result = max(dp1[n-2], dp2[n-1]) $

🧩 코드