[프로그래머스] Lv3. 스티커 모으기(2)- JavaScript

문제분류 : 코팅테스트 연습

난이도 : Level 3

출처 : 프로그래머스 - 스티커 모으기

문제

제한사항

📌 내가 생각한 풀이

첫번째 스티커를 뜯는 경우, 뜯지 않는 경우를 나누고, i번째 스티커를 때는데까지 온 최대값은 i-2번째 스티커를 때는데까지 온 최대값에다가 i번째 스티커값을 더한것과, i-1번째 스티커를 때는데까지 온 최대값을 비교하여 그 중 최대값을 i번째 값으로 하는 Dynamic Programming을 이용하여 답을 구하자.

function solution(sticker) {
    var answer = 0;
    
    if(sticker.length === 1){
        return answer = sticker[0]
    }
    //첫번째 스티커를 땠을경우
    let dp1 = new Array(sticker.length).fill(0);
    dp1[0] =sticker[0];
    dp1[1] = sticker[0];
    //첫번쨰 스티커를 안땠을경우
    let dp2 = new Array(sticker.length).fill(0);
    dp2[1] = sticker[1];
    
    for(var i =2; i<sticker.length; i++){
        // i번째 스티커까지 때는데 최대값은 i-2번째 스티커까지 땐 최대값 + i번째 스티커 값과
        // i-1번째 스티커까지 땐 최대값중 더 큰값이다.
        dp1[i] = Math.max(dp1[i-2]+sticker[i], dp1[i-1]);
    }
    for(var i = 2; i<sticker.length; i++){
        // i번째 스티커까지 때는데 최대값은 i-2번째 스티커까지 땐 최대값 + i번째 스티커 값과
        // i-1번째 스티커까지 땐 최대값중 더 큰값이다.
        dp2[i] = Math.max(dp2[i-2]+sticker[i], dp2[i-1])
    }
    //dp1[sticker.length-2]인 이유 -> dp1은 첫번째 스티커를 땐 경우라고 가정했으므로, circular buffer처럼 마지막 가장 마지막스티커는 땔 수 없다. 따라서 sticker.length-2번째가 최대값이다.
    //dp1[sticker.length-1]인 이유 -> dp2는 첫번째 스티커를 때지 않고 두번쨰 스티커부터 땐 경우의 수이므로 마지막 스티커를 땔 수 있다.
    return answer = Math.max(dp1[sticker.length-2], dp2[sticker.length-1])
    

}

📌 느낀점

문제를 보자마자, 다이나믹 프로그래밍이란 걸 알았고, 첫번째 스티커를 땐 경우와, 때지않는 경우를 나누어 풀어야함을 알았다. 하지만, dp의 점화식을 세우는데 조금 시간이 오래걸렸고, 아직 dp가 약하다는 것을 느꼈다.