[JS] 도둑질

DP를 활용한 문제였다.

 

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

프로그래머스

 

 

 

직선형인 집이었다면 조금더 쉬웠겠지만 원형이기때문에 조금 생각을 해줘야 하는 DP문제였다.

 

 

1. 첫집을 터는 경우 -> 마지막 집과 두번째 집을 털면 안된다.

2. 첫집을 털지 않는 경우 -> 두번째 집 ~ 마지막집까지만 계산하면 된다.

 

dp를 이차원 배열로 두고

 

dp[i][0] -> i번째 집을 털었다고 가정했을 때의 최댓값

dp[i][1] -> i번째 집을 털지 않았다고 가정했을 때의 최댓값

 

이라 생각해보자.

 

dp[i][0] -> dp[i-1][1] + money[i] 이다.

전집을 털지않았을때의 최댓값 + i번째 집을 털어 나온값.

 

dp[i][1] -> Math.max(dp[i-1][0] , dp[i-1][1])

i번째 집을 털지 않으니 이전 집을 털든말든 유무와 상관없이 큰 값을 가져오면 된다.

 

 

 

따라서 이렇게 문제를 풀면 해결되는데 시간초과가 났다. 어차피 최대값만 구하면 되므로 위 원리를 유지한 뒤 변수의 값을 갱신하는 방법으로 구현해서 해결하였다!

 

 

 

 

 

function solution(money) {
    const {length} = money
    let ret = 0
    //첫집을 턴 경우
    let still = -99999
    let noneStill = money[0]
    
    for (let i = 2; i < length-1 ; i++) {
        const nxStill = noneStill + money[i]
        const nxNoneStill = Math.max(still,noneStill)
        still = nxStill
        noneStill = nxNoneStill
    }
    ret = Math.max(still,noneStill)
    //첫집을 안턴 경우
    still = 0
    noneStill = 0
    for (let i = 1; i < length ; i++) {
        const nxStill = noneStill + money[i]
        const nxNoneStill = Math.max(still,noneStill)
        still = nxStill
        noneStill = nxNoneStill
    }
    
    return Math.max(still,noneStill,ret)
}