[DP] 스티커 모으기(2), 도둑질

 

https://school.programmers.co.kr/learn/courses/30/lessons/12971

프로그래머스

 

문제 설명

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

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

예를 들어 위 그림에서 14가 적힌 스티커를 뜯으면 인접해있는 10, 6이 적힌 스티커는 사용할 수 없습니다. 스티커에 적힌 숫자가 배열 형태로 주어질 때, 스티커를 뜯어내어 얻을 수 있는 숫자의 합의 최댓값을 return 하는 solution 함수를 완성해 주세요. 원형의 스티커 모양을 위해 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어 있다고 간주합니다.

제한 사항

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

 

첫번째 풀이

DP특징 최대값 최솟값을 구해라~

주의

꼭 1개씩 띄어서 고르는게 아니라, 합이 크고 인접하지 않는 큰 수를 고르는 것이다.

예를 들어 14, 2, 20, 90, 10 이면 당연히 14, 20 이렇게나 2, 90 이 아닌 14, 90 이렇게 고른다

 

로직

dp[i] 에 저장하는건 i 스티커까지 뜯었을 때의 최댓값을 의미한다

작은걸로 큰걸 만들수 있는 점화식 만들기

memo[i] = Math.max(memo[i-1], memo[i-2] + sticker[i])
현재위치까지 최대값 = max(전 위치까지의 최대값, 전전 위치까지의 최대값 + 현재값)

 

dp[i-1]의 의미는 현재 뜯어야 할 스티커가 i번째 일 때, 이미 이전의 스티커까지 뜯었을 때의 최댓값을 의미한다.

따라서 i번째 바로 직전의 스티커를 뜯었으므로 현재 i번째 스티커는 뜯을 수가 없다.

따라서 i번째의 최댓값은 당연히 이전의 최댓값과 동일하게 될 것이다.

 

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

 

첫 번째 스티커는 뜯을 수도 있고, 뜯지 않을 수도 있다, 따라서 1번째 스티커를 뜯은 dp1배열과,  2번째 스티커를 뜯은 dp2배열을 따로 구한다. 

 

 

1. dp를 만들때,  i = 0부터 점화식에 대입하면 i-2 는 음수이므로 dp의 길이를 len = sticker길이 + 2로 만들어준다.

2. dp1은 첫번째 스티커를 선택하고 마지막은 선택하지 않으므로 i의 범위는 2 <= i < len-1 다.

3. dp2는 두번째 스티커를 선택하고 마지막도 선택하므로 i의 범위는 3 <= i < len 다.

4. 각각 dp1, dp2에서 큰 숫자들 중 최대값을 리턴한다.

 

시간초과 방지

sort, Math.max, min 사용 줄이기

 

function solution(sticker) {
    var answer = 0;
    const len = sticker.length+2;
    const dp1 = new Array(len).fill(0); // 1번째 스티커를 뽑았을때 
    const dp2 = new Array(len).fill(0); // 2번째 스티커를 뽑았을때
    
    if(sticker.length <= 2) return Math.max(...sticker); //

    // 1번째 뽑았을때 마지막 스티커는 뽑지 않는다
    for (let i = 2; i < len-1; i++) {
        dp1[i] = Math.max(dp1[i-1], dp1[i-2] + sticker[i-2])
    }
    
    // 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]); // dp1은 마지막 스티커를 안 뽑았으니 마지막에서 두번째인 (len-1)-1 
}

 

dp의 코드는 짧고 간단하지만 강력하다. 신기하다.

 

---

같은 유형의 문제 

 

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

프로그래머스

function solution(money) {
    var answer = 0;
    const len = money.length + 2
    const dp1 = Array.from({length: len}, () => 0);
    const dp2 = Array.from({length: len}, () => 0);
    
    for (let i = 2; i < len-1; i++) {
        dp1[i] = Math.max(dp1[i-1], dp1[i-2] + money[i-2]);
    }
    for (let i = 3; i < len; i++) {
        dp2[i] = Math.max(dp2[i-1], dp2[i-2] + money[i-2]);
    }
    return Math.max(dp1[len-2], dp2[len-1]);
}