[프로그래머스 알고리즘] 스티커모으기(2) JavaScript JS

프로그래머스

😉문제 풀이 설명

위 문제는 DP문제입니다.

따라서 점화식을 구하고, 이에 따른 코드를 작성할 필요가 있습니다.

점화식은 다음과 같습니다.

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

---

🤨주의 사항

dp[i] 배열을 순회할 때 참조하는 인덱스는 i-1과 i-2입니다. 따라서 dp 배열의 0번째 인덱스와 1번째 인덱스는 값을 채워주고 순회를 시작해야 합니다.

문제에서 스티커는 원형으로 연결되어 있습니다. 따라서 첫 번째 스티커를 떼는 경우와 떼지 않는 경우 두 가지를 생각하여야 합니다.

//첫 번째 스티커를 떼는 경우
const dp1 = [sticker[0],sticker[0],...Array(length-2).fill(0)];

//첫 번째 스티커를 떼지 않는 경우
const dp2 = [0,sticker[1],...Array(length-2).fill(0)];

---

😎문제 풀이 코드

function solution(sticker) {
    const length = sticker.length;
    if(length === 1) return sticker[0]
    const dp1 = [sticker[0],sticker[0],...Array(length-2).fill(0)];
    const dp2 = [0,sticker[1],...Array(length-2).fill(0)];

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

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