https://school.programmers.co.kr/learn/courses/30/lessons/42897
문제
> 도둑이 어느 마을을 털 계획을 하고 있습니다.
> 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.
> 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.
> 각 집에 있는 돈이 담긴 배열 money가 주어질 때,
도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.접근
선형이 아닌 원형 관계이므로 만약 첫 집을 털면 마지막 집도 인접한 집이므로 털 수 없다. 마찬가지로 마지막집을 털면 첫집을 털 수 없다.
따라서 첫집을 털고, 마지막집을 안터는 경우와 첫집을 건너뛰고 마지막집을 터는 경우를 각각 구한 뒤 더 큰 값을 반환한다.
문제해결
> 첫 집을 털었을 때의 dp1과, 마지막집을 털었을 때의 dp2를 선언한다.
> dp1은 첫집을 털기 때문에 dp1[0]과 dp1[1]은 1번집 가격이 된다.
1번집을 반드시 털고, 2번집은 인접집이라 못털기 때문이다.
> dp2는 첫집안털고 2번 째 집부터 털기 때문에 두번 째 집 가격부터 시작한다.
> 이제 세번째 집부터 반복을 돌며 선형일 때와 동일한 방법으로 dp를 구한다.
> 현재 번째 집을 안털어서 온 i-1과 현재집을 털어 i-2에 현재집의 가격이 더해진값을 최대값연산한다.
> 이 때, dp1은 마지막집을 안털기 위해 마지막은 건너 뛴다.
> dp1은 size-2가 최종 값이고(마지막 집은 안털기 때문에), dp2는 size-1이 최종 값이므로 둘 중 큰값을 반환한다.코드
class Solution {
public int solution(int[] money) {
int size = money.length;
int[] dp1 = new int[size]; //첫 집 털
int[] dp2 = new int[size]; //첫 집 안털
dp1[0] = dp1[1] = money[0]; //첫집 털어서 가격 누적
dp2[1] = money[1]; //두번째 집부터 터니까 가격 누젹
for(int i = 2; i < size ; i++) {
dp2[i] = Math.max(dp2[i-1], dp2[i-2] + money[i]);
if(i == size -1) continue;
dp1[i] = Math.max(dp1[i-1], dp1[i-2] + money[i]);
}
return Math.max(dp1[size-2], dp2[size-1]);
}
}
후기
전에 색상환 문제를 경험해봐서 원형으로 주어질 때의 풀이방법을 어느정도 알고 있었다.접근은 어렵지 않았지만 다시 접근해보니 좀 논리가 꼬여 새로 공부하는 기회였다.
