(javascript) 알고리즘 - 스티커 모으기 (완벽설명, 이해)

문제 설명

N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다.

원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 하고 싶습니다. 단 스티커 한 장을 뜯어내면 양쪽으로 인접해있는 스티커는 찢어져서 사용할 수 없게 됩니다.

예를 들어 위 그림에서 14가 적힌 스티커를 뜯으면 인접해있는 10, 6이 적힌 스티커는 사용할 수 없습니다.

스티커에 적힌 숫자가 배열 형태로 주어질 때, 스티커를 뜯어내어 얻을 수 있는 숫자의 합의 최댓값을 return 하는 solution 함수를 완성해 주세요.

원형의 스티커 모양을 위해 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어 있다고 간주합니다.

 

• 제한 사항
  • sticker는 원형으로 연결된 스티커의 각 칸에 적힌 숫자가 순서대로 들어있는 배열로, 길이(N)는 1 이상 100,000 이하입니다.
  • sticker의 각 원소는 스티커의 각 칸에 적힌 숫자이며, 각 칸에 적힌 숫자는 1 이상 100 이하의 자연수입니다.
  • 원형의 스티커 모양을 위해 sticker 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어있다고 간주합니다.

 

• 입출력 예

sticker	answer
[14, 6, 5, 11, 3, 9, 2, 10]	36
[1, 3, 2, 5, 4]	8

1. 입출력 예 #1 : 6, 11, 9, 10이 적힌 스티커를 떼어 냈을 때 36으로 최대가 됩니다.
2. 입출력 예 #2 : 3, 5가 적힌 스티커를 떼어 냈을 때 8로 최대가 됩니다.

---

접근 방법

먼저 이 문제는 DP로 접근해야 풀 수 있습니다. 

DP에 대한 설명은 아래 포스팅을 참고하시면 됩니다.

[알고리즘] 동적 프로그래밍 (DP) 란? feat.동적 계획법

 

이 문제를 DP로 접근할 수 있는 이유는

인접한 스티커는 뜯지 않는 조건으로 스티커를 한장씩 뜯어 얻을 수 잇는 최댓값을 구해하는데,

이 과정이 누적합을 구하는 방식과 유사하기 때문입니다.

 

현재 뜯은 스티커 + 다음에 뜯을 스티커 의 누적합이 최대값이 되는 경우를 찾아야 하는 것이기 때문에,

이전에 구해놓은 값을 활용하는 형태가 되므로 DP의 조건이 충족되게 됩니다.

 

자세한 설명은 아래 코드를 참고하며 설명드리겠습니다.

---

solution.js

function solution(sticker) {
  
    /* 점화식에서 i-2 값을 구하기 때문에 마이너스 값을 인덱스를 가르키는 것을 방지하고자 +2 */
    const len = sticker.length + 2;

    /* 스티커의 개수 만큼의 DP 배열을 모두 0으로 초기화 */
        // 1번째 스티커를 뜯는 dp배열
    const dp1 = new Array(len).fill(0);
        // 1번째 스티커를 뜯지 않는 dp배열
    const dp2 = new Array(len).fill(0);

    console.log(dp1)
    console.log(dp2)
    
        // 스티커가 하나밖에 없을 경우
    if(sticker.length === 1) return sticker[0];
    
    /* 1번째 스티커를 뜯는 경우 */ 
        // 마지막 스티커와 인접하므로 len-1 까지 반복한다.
    for(let i = 2; i < len-1; i++)
        // DP 배열의 크기가 +2 되었으므로 해당 스티커 역시 sticker[i-2]로 찾아야 한다.
      dp1[i] = Math.max(dp1[i-1], dp1[i-2] + sticker[i-2]);

    console.log(dp1)


    /* 2번재 스티커를 뜯는 경우 */
        // 마지막 스티커와 인접하지 않으므로 len 까지 반복하며, i는 3부터 시작한다.
    for(let i = 3; i < len; i++) 
        // DP 배열의 크기가 +2 되었으므로 해당 스티커 역시 sticker[i-2]로 찾아야 한다.
      dp2[i] = Math.max(dp2[i-1], dp2[i-2] + sticker[i-2]);

    console.log(dp2)
    
    /* 두 경우 중 최대값을 반환 */
    return Math.max(dp1[len-2], dp2[len-1]);
  }

 

DP 점화식
dp[i] = Math.max(dp[i-1], dp[i-2] + sticker[i]);

dp[i-1] : 현재 뜯어야 할 스티커가 i번째 일 때, 이미 이전의 스티커까지 뜯었을 때의 최댓값을 의미한다.
따라서 i번째 바로 직전의 스티커를 뜯었으므로 현재 i번째 스티커는 뜯을 수가 없다.
따라서 i번째의 최댓값은 당연히 이전의 최댓값과 동일하게 될 것이다

dp[i-2] : 한 칸 건너뛰어 그 이전의 스티커를 뜯었을때 까지의 최댓값을 의미한다.
즉 인접한 스티커가 아니기 때문에 현재 스티커 sticker[i]를 뜯을 수 있다.
따라서 이 둘의 합이 최댓값이 될 수 있는 수가 될 것이다.

 

코드 해설

주어진 sticker 는 [14, 6, 5, 11, 3, 9, 2, 10] 이라고 가정하여 설명하겠습니다.

---

1️⃣ 스티커의 길이에 +2를 한 이유는 점화식에서 i - 2 의 값을 구해주는데 현재 문제 예시의 sticker 길이는 8인데,

원래 길이에서첫 번째에서 시작할 시 i - 2를  구할시 - 값 인덱스가 나오기 때문에 2만큼 더해줍니다.

const len = sticker.length + 2;

 

2️⃣ dp1 은 1번째 스티커를 뜯는 dp배열을 말하고, dp2는 2번째 스티커를 뜯는 dp배열을 의미합니다.

누적합을 새로 채워 넣기위해 len 크기 만큼 새로운 배열을 생성하고, fill 메서드로 배열에 0을 채워넣습니다.

const dp1 = new Array(len).fill(0);
const dp2 = new Array(len).fill(0);

• 길이가 10인 다음과 같은 배열을 가지게 됩니다. [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]

 

3️⃣  스티커가 하나밖에없다면 최대값은 그 자체가 최대값이므로 바로 리턴합니다.

if(sticker.length === 1) return sticker[0];

 

4️⃣  1번째 스티커를 뜯는 경우 반복문으로 첫번째 스티커는 마지막 스티커와 인접하므로 len-1 까지 반복합니다.

i 가 2부터 시작하는 이유는 sticker.length + 2 로 배열의 크기를 2만큼 늘렸기 때문입니다. ( 원래 길이 대로면 i = 2 는 i = 0 번째인 것입니다. )

sticker.length + 2 로 배열의 크기가 2가 늘었기 때문에 주어진 sticker 의 원래 배열 ( sticker[i - 2] )로 찾습니다.

for(let i = 2; i < len-1; i++)
  dp1[i] = Math.max(dp[i-1], dp[i-2] + sticker[i-2]);

 

 

이 반복문이 끝나면 다음과 같은 배열을 갖습니다. [ 0, 0, 14, 14, 19, 25, 25, 34, 34, 0 ]

 

5️⃣  2번째 스티커를 듣는 경우의 반복 문으로 마지막 스티커와 인접하지 않아 마지막 스티커 위치인 len 까지 반복합니다.

i 가 3부터 시작하는 이유는 sticker.length + 2 로 배열의 크기를 2만큼 늘렸기 때문에 원래 2번째 스티커인 i =1 에도 2를 더한 값입니다.

마찬가지로 sticker.length + 2 로 배열의 크기가 2가 늘었기 때문에 주어진 sticker 의 원래 배열 ( sticker[i - 2] )로 찾습니다.

for(let i = 3; i < len; i++)
  dp2[i] = Math.max(dp[i-1], dp[i-2] + sticker[i-2]);

 

이 반복문이 끝나면 다음과 같은 배열을 갖습니다. [ 0, 0, 0, 6, 6, 17, 17, 26, 26, 36 ]

 

6️⃣  마지막으로 구해진 dp1, dp2 배열 중 가장 큰 값을 리턴합니다.

dp1[len - 2] 는  마지막 스티커를 때지못하므로 위 dp1의 배열을 보면 알 수 있듯이 len - 2 ( i = 8 )위치에 최댓값이 있기 때문입니다.

dp2[len - 1] 은 마지막 스티커를 땔수 있으므로 위 dp2의 배열을 보면 알 수 있듯이 len - 1 ( i = 9 )위치에 최댓값이 있기 때문입니다. 

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

 

---

 

참고자료
https://velog.io/@longroadhome/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LV.3-%EC%8A%A4%ED%8B%B0%EC%BB%A4-%EB%AA%A8%EC%9C%BC%EA%B8%B0-JS