(프로그래머스 JS)스티커 모으기(2)

https://programmers.co.kr/learn/courses/30/lessons/12971?language=javascript 

코딩테스트 연습 - 스티커 모으기(2)

DP를 이용한 문제 풀이.

하나의 스티커를 땠을 때, 양 옆의 스티커를 사용하지 못하기 때문에 DP 테이블을 2개 사용해야 한다.

 

왜냐하면 아래처럼 두 가지 경우 중 합이 큰 값을 골라야 하기 때문이다.

1) 첫번째 스티커부터 땠을 때(가장 마지막에 있는 스티커를 사용하지 못함)

2) 두번째 스티커부터 땠을 때(가장 처음에 있는 스티커를 사용하지 못함)

 

즉, 두 가지 경우에서 가장 많은 스티커를 때면서 가장 큰 값을 찾아야 한다.

 

dp1은 1의 경우를 고려한 테이블,

dp2은 2의 경우를 고려한 테이블이다.

 

for문을 돌 때 인덱스 2부터 시작한다.

점화식인 dp[i - 1]과 dp[i - 2] + sticker[i] 중 더 큰 값을 테이블에 저장하면 된다.

단, 1)의 경우는 가장 마지막에 있는 스티커를 사용하지 못하기 때문에 if문으로 조건을 걸어서 최대값을 dp 마지막 인덱스에 저장한다.

 

for문이 끝나면 두 개의 dp 테이블의 마지막 인덱스 값 중 최대값을 고르면 된다.

const solution = (sticker) => {
    const length = sticker.length;
    const dp1 = Array(length).fill(0);
    const dp2 = Array(length).fill(0);
        
    dp1[0] = sticker[0];
    dp1[1] = sticker[0];
    dp2[1] = sticker[1];

    for(let i = 2; i < length; i++){
        if(i !== length - 1){
            dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + sticker[i]);
        } else{
            dp1[i] = dp1[i - 1];
        }
        
        dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + sticker[i]);
    }

    return Math.max(dp1[length - 1], dp2[length - 1]);
}