[프로그래머스] 도둑질

문제 설명

도둑이 마을의 집을 털려고 한다. 마을의 집은 원의 형태로 처음 집과 끝 집이 이어진 형태로 위치하고 있다.
마을에는 특이한 방범 시스템이 있는데 인접한 집을 털면 경보가 울리게 된다. 도둑은 이 사실을 알고 있어서 인접한 집을 털지 않고 최대한 많은 돈을 훔치려고 한다. 각 집의 훔칠 수 있는 돈의 정보가 주어졌을 때 도둑이 최대로 훔칠 수 있는 돈을 출력하는 문제다.

문제 풀이

DP로 문제에 접근해야 한다. 인접한 집을 털지만 않으면 되기 때문에 현재 털고 있는 집에서 두 칸 이상 떨어진 집은 고려하지 않아도 된다. 현재 집을 털 때 고려해야 할 것은 전전집과 현재 집을 털었을 때의 누적합이 현재집을 털지 않고 이전집까지의 누적합과 비교해서 현재집까지의 누적합을 테이블에 채워넣으면 된다.

이 것을 점화식으로 바꾸면 이렇게 작성할 수 있다.

dp[i] = Math.max(dp[i-2] + money[i], dp[i-1])

dp[i]가 의미하는 바는 i 집까지 도둑질을 했을 때 최대 누적합이다. 따라서 dp[i] 값은 dp[i-2] + money[i] 전전집까지의 누적합과 현재 집을 털 때의 돈과 dp[i-1] 현재 집을 털지 않고 이전 집까지 털었을 때의 돈을 비교한다.

이 문제에서 또 고려해야 할 점은 집이 놓여진 방식이다. 결론부터 말하자면 이 문제는 두개의 DP 테이블을 생성해야 한다. 첫 번째 집을 털었을 때(=마지막 집을 털지 않을 때)와 첫 번째 집을 털지 않을 때(=마지막 집을 털 수도 있을 때)로 구분해야 한다. 집들이 원의 형태로 첫 번째 집과 마지막 집이 인접한 형태로 되어 있다. 첫 번째 집과 마지막 집은 인접하기 때문에 둘 모두를 더하는 경우를 제외해야 한다. 첫 번째 집부터 마지막 집까지 반복문을 돌릴 때 범위를 마지막 집까지 설정한다면 첫 번째 집과 마지막 집을 동시에 터는 경우가 발생한다. 그렇다고 반복문의 범위를 마지막 집을 제외한다면 마지막 집을 터는 경우를 고려할 수가 없다. 때문에 dp1 첫 번째 집을 털었을 때, dp2 첫 번째 집을 털지 않았을 때의 테이블을 생성해주었다. 그리고 dp1[0]과 dp1[1]은 첫 번째 집을 털었을 때로 고정해주었다. 그리고 dp2[1]은 첫 번째 집을 털지 않고 두번 째 집을 털었을 때로 고정해주었다.

위의 내용을 정리하면 이렇게 코드를 작성할 수 있다.

const dp1 = Array(money.length).fill(0)
const dp2 = Array(money.length).fill(0)

dp1[0] = money[0]
dp1[1] = money[0]
dp2[1] = money[1]

점화식과 초기값을 설정해주었고 반복문을 통해서 첫 번째 집부터 마지막 집까지의 최대누적합을 구하면 된다.
dp1과 dp2를 따로 돌려줄 수 도 있지만 시간 초과가 발생해서 같은 for문 안에서 값을 구해주었다.

// 첫 번째 집과 두 번째 집은 미리 설정해주었기 때문에 i = 2 부터 반복문을 돌려준다.
// dp2의 겨우 마지막집까지 고려해주어야 하기 때문에 i < money.length로 범위를 설정해주었다.
for (let i = 2; i < money.length; i++) {
  dp1[i] = Math.max(dp1[i-2], money[i], dp1[i-1])
  dp2[i] = Math.max(dp2[i-2], money[i], dp2[i-1])
}

그리고 dp1은 마지막 집까지 합해진 경우가 추가되었으므로 dp1[money.length-2]까지의 최대 누적합을 dp2[money.length-1]과 비교해준다.

return Math.max(dp1[money.length-2], dp2[money.length-1])

제출 코드

function solution(money) {
    const len = money.length
    const dp1 = Array(len).fill(0)
    const dp2 = Array(len).fill(0)
    dp1[0] = money[0]
    dp1[1] = money[0]
    dp2[1] = money[1]
    for (let i = 2; i < len - 1; i++) {
        dp1[i] = Math.max(dp1[i-2] + money[i], dp1[i-1])
        dp2[i] = Math.max(dp2[i-2] + money[i], dp2[i-1])
    }
    return Math.max(dp1[len-2], dp2[len-1])
}

출처: 프로그래머스 - https://school.programmers.co.kr/learn/courses/30/lessons/42897