문제
도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.
각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.
각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.
제한
- 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
- money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.
입출력 예시
| money | return |
|---|---|
| [1, 2, 3, 1] | 4 |
풀이
코딩테스트 고득점 Kit 동적계획법으로 분류된 문제이다. 아쉽게 자바스크립트로는 풀이환경을 제공하지 않지만 JS로 풀어보자. DP 문제이면서 제한사항 역시 자바스크립트로 통과 가능할 정도의 크기이므로 직접 테스트해볼 수는 없겠지만 풀이가 가능할 것으로 생각된다. 이 문제는 앞서 풀어본 Lv.3 난이도의 이 문제와 유사하다. 그런데 문제가 오래되어 그런지 동일한 문제임에도 서로 난이도가 다르게 측정되어 있다.
1) 인접한 집
먼저 인접한 집은 도둑질을 할 수 없다. 어떤 원리인지는 모르겠지만 인접한 집끼리는 방범 장치가 연결되어 있기 때문이란다. 따라서 만약 내가 첫 번째 집을 털었다면, 두 번째 집은 시도할 수 없고 세 번째 집부터 다시 도둑질을 할 수 있다.
해당 조건은 위에 링크된 문제와 완전히 동일한 조건이다. 즉 따라서 우리는 다음과 같은 두 가지 분기점으로 나누어 생각할 수 있다.
- 첫 번째 집을 방문했을 경우
- 첫 번째 집을 방문하지 않았을 경우
또한 DP배열 역시 동일하게 생각할 수 있다. DP[i]는 i번째 집을 방문했을때의 최대값으로 생각하고 이에 대한 누적합을 구해주도록 하자. 다만 연달아 집을 털 수는 없기 때문에 Math.max(DP[i-2] + money[i], DP[i-1])을 통해 현재 DP[i]의 최대값을 갱신해주어야 한다.
DP[i]의 시점에서도 마찬가지로 두 가지 분기점이 존재하는데, 만약 이전 집을 털었을 경우와 털지 않았을 경우로 나뉘게 된다. 이전 집을 털었다면 현재 집은 털 수 가 없다. 따라서 그대로 DP[i-1]의 값을 유지해야 한다. 반면 이전 집을 털지 않았다면 지금 방문하는 집을 털 수 있다. 이때 최대값이 되기 위한 조건은 전전집까지 도둑질을 한 금액(= DP[i-2])와 현재 집에서의 금액의 합이 될 것이다. 이처럼 DP 배열도 분기가 나뉘기 때문에 2개의 DP 배열을 선언해주도록 하자.
2) 점화식
DP[i] = Math.max(DP[i-2] + money[i], DP[i-1]);점화식인 앞서 살펴본 바와 같다. 따라서 위와 같은 점화식을 구할 수 있다. 다만 두 개의 DP 배열이 있고 이 둘의 시작점이 다르기 때문에 이들의 범위만 살짝 다르게 설정해주어야 한다. DP배열의 경우는 집의 개수와 동일한 크기로 2개를 선언해주자.
const dp1 = new Array(money.length).fill(0);
const dp2 = new Array(money.length).fill(0);1. 첫번째 집을 방문하는 경우
첫번째 집을 방문한다면 당연히 마지막 집을 방문할 수 없다. 따라서 이 경우엔 집의 개수 - 1 보다 작은 범위 내에서 반복문을 돌아야 할 것이다.
또한 DP[0] = DP[1] = money[0]이 성립한다. 첫번째 집을 방문하므로 이 시점에서의 DP배열인 DP[0]은 당연히 첫 번째 집의 금액이 저장될 것이다. 그리고 그 다음 집은 방문할 수 없기에 DP[1]은 이전 값과 동일할 것이다. 따라서 이 경우에는 다음과 같이 반복문을 돌며 값을 구해주자.
const len = money.length;
// 첫 집을 방문하므로 dp1[0]과 dp1[1] 모두 첫 집의 금액과 같다.
dp1[0] = dp1[1] = money[0];
// 처음 두 집은 초기화가 완료되었으므로
// 그 이후에 있는 집부터 점화식을 적용한다.
// 다만 마지막 집은 방문할 수 없으므로 len-1 까지 반복
for(let i = 2; i < len-1; i++) {
dp1[i] = Math.max(dp1[i-2] + money[i], dp1[i-1]);
}
2. 첫번째 집을 방문하지 않는 경우
첫번째 집을 방문하지 않는다면 당연히 마지막 집을 방문할 수 있다. 따라서 이 경우엔 집의 개수만큼 반복문을 돌며 점화식을 통해 값을 구해주면 된다.
다만 이때는 첫 번째 집을 방문하지 않기 때문에 DP[0] = 0이 된다. 그리고 DP[1] = money[1]로 초기화 후 다음과 같이 반복문을 돌 수 있다.
// 첫 번째 집을 방문하지 않을 때의 초기값 설정
dp2[0] = 0;
dp2[1] = money[1];
// 역시 처음 두 집은 초기화가 완료되었으므로
// 그 이후에 있는 집부터 점화식을 적용한다.
// 이때 마지막 집을 방문할 수 있기때문에 len까지 반복
for(let i = 2; i < len; i++) {
dp2[i] = Math.max(dp2[i-2] + money[i], dp2[i-1]);
}
3) 정답
정답은 당연히 dp1과 dp2 둘 중에서 가장 큰 값을 리턴해주면 될 것이다. 하지만 마지막까지 주의하자. 첫번째 경우는 마지막 집을 방문하지 못했기 때문에 최대값이 DP[len-2]위치에 담겨있을 것이고, 두번째 경우는 마지막 집을 방문했기 때문에 최대값이 DP[len-1]위치에 담겨있다. 이 둘을 비교해 최대값을 반환하도록 하자.
return Math.max(dp1[len-2], dp2[len-1]);4) 전체코드
이보다 상세한 설명은 앞서 링크를 건 포스트에서 이미 했기때문에 간략하게 넘어갔다. 만약 이해가 되지 않는 부분이 있다면 앞서 링크된 게시물을 참고하자. (방식이 사~알짝 다르긴한데 중추적인 로직은 동일하다. 궁금하면 직접 참고해보자!) 자바스크립트 환경이 제공되지 않아 직접 테스트는 해보지 않았지만, 동일한 로직으로 JAVA로 작성한 코드는 통과하는 것을 확인했다. 주석을 제외하 전체코드는 다음과 같다.
function solution (money) {
const len = money.length;
const dp1 = new Array(len).fill(0);
const dp2 = new Array(len).fill(0);
dp1[0] = dp1[1] = money[0];
for(let i = 2; i < len-1; i++) {
dp1[i] = Math.max(dp1[i-2] + money[i], dp1[i-1]);
}
dp2[0] = 0;
dp2[1] = money[1];
for(let i = 2; i < len; i++) {
dp2[i] = Math.amx(dp2[i-2] + money[i], dp2[i-1]);
}
return Math.max(dp1[len-2], dp2[len-1]);
}
출처
