[JS] 스티커모으기(2)

dp를 활용하여 해결하였다.

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

프로그래머스

 

 

처음에 dp를 활용하여 해결하려 했다.

 

2차원 배열의 dp를 활용하여 dp[i] = [a,b] 라는 꼴을 두었을때

i번째 스티커까지의 최고합 = [ i번째 스티커를 찢은경우 , i번째 스티커를 찢지 않은경우 ]

이런식으로 스티커를 찢은 경우와 안찢은 경우를 기록해나가며 문제를 해결하였다.

 

이때 dp[i][0] = dp[i-1][1] + sticker[i] 라는 점화식이 나온다.

즉 스티커를 찢은경우 = 이전스티커를 안찢은 경우 + 찢은 현재 스티커의 숫자

 

스티커를 안찢은 경우 dp[i][1] = Math.max(...dp[i-1]) 라는 점화식이 나온다.

이전 스티커를 찢든 안찢든 더 큰 값을 가져오면 된다.

 

 

여기까지가 기본 원리이고 해당 문제는 스티커가 원형으로 주어지기때문에 시작스티커를 찢고 시작하는 경우와 시작스티커를 안찢고 시작하는 경우 2가지로 시작점을 나누고 시작하면 문제를 해결할 수 있다.

 

1. 시작스티커를 찢는경우 -> 2번째 스티커를 무조건 안찢는걸로 시작하며, 마지막 스티커를 사용할 수 없음

2. 시작스티커를 찢지않는 경우 -> 첫번째 스티커를 무조건 0처리 하며, 마지막 스티커까지 순회

 

 

이렇게 구현했는데 처음에 시간초과가 나서 배열을 사용하지 않고 값을 갱신시키는 방법으로 코드를 구현했더니 통과했다.

 

 

 

 

function solution(sticker) {
    const len = sticker.length
    
    //첫스티커 뗀 경우
    let tmp = [0,sticker[0]]
    
    for (let i = 2 ; i < len-1 ; i++){
        tmp = [tmp[1] + sticker[i],Math.max(...tmp)]
    }
    
    //첫 스티커 안뗀 경우
    let tmp2 = [0,0]
    
    for (let i = 1 ; i < len ; i++){
        tmp2 = [tmp2[1] + sticker[i],Math.max(...tmp2)]
    }
    return Math.max(...tmp,...tmp2)

}