프로그래밍 강의 / 알고리즘 문재 해설 / 스티커 모으기

문제 설명

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

원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에

적힌 숫자의 합이 최대가 되도록 하고 싶습니다.

 

단 스티커 한 장을 뜯어내면 양쪽으로 인접해있는 스티커는 찢어져서 사용할 수 없게 됩니다.

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

스티커에 적힌 숫자가 배열 형태로 주어질 때, 스티커를 뜯어내어 얻을 수 있는 숫자의

합의 최댓값을 return 하는 solution 함수를 완성해 주세요.

 

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

 

제한 사항

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

 

문제 풀이 방법

• DP(Dynamic Programming) 자료구조 을 이용해 풀어야한다
  (단순 그리디 방법으로 하게되면 문제 해결이 안된다.)
• 한개를 뜯으면 양쪽은 사용하지 못하므로 이에 맞는 로직을 구성해야된다.
• 함수에서 사용할 배열은 첫번째를 뜯을 경우를 생각해서 +2 길이로 구성한다.
• dp[i-1]의 의미는 현재 뜯어야 할 스티커가 i번째 일 때,
  이미 이전의 스티커까지 뜯었을 때의 최댓값을 의미한다.
  따라서 i번째 바로 직전의 스티커를 뜯었으므로 현재 i번째 스티커는 뜯을 수가 없다.
  따라서 i번째의 최댓값은 당연히 이전의 최댓값과 동일하게 될 것이다.
• 반면 dp[i-2]의 경우는 한 칸 건너뛰어 그 이전의 스티커를 뜯었을때 까지의 최댓값을 의미한다.
  즉 인접한 스티커가 아니기 때문에 현재 스티커 sticker[i]를 뜯을 수 있다.
  따라서 이 둘의 합이 최댓값이 될 수 있는 수가 될 것이다.

 

 

 

 

내가 작성한 코드

const solution = (sticker) => {
    //  +2 한 이유는 첫 번째부터 회수 할 때 이전 값들과 비교를 위해 0을 넣기 위해
    const len = sticker.length + 2;
    let dp1 = new Array(len).fill(0);
    let dp2 = new Array(len).fill(0);
    
    if(sticker.length === 1){
        return sticker[0];
    }
    //  로직 설명
    //  한개를 뜯으면 양 옆의 것들은 사용할 수 없기 때문에
    //  뜯게되면 이전 값들과 비교하며 더한 겂을 dp에 저장
    //  첫 번째 스티거 부터 회수 시
    for(let i=2; i<len-1; i++){
        dp1[i] = Math.max(dp1[i-1], dp1[i-2] + sticker[i-2]);
    }
    //  두 번째 스티커 부터 회수 시
    for(let i=3; i<len; i++){
        dp2[i] = Math.max(dp2[i-1], dp2[i-2] + sticker[i-2]);
    }
    return Math.max(dp1[len-2], dp2[len-1]);
}