[Programmers, C++]#Level3_스티커 모으기(2), 동적 계획법, DP, Dynamic Programming, 점화식

#1. 문제

프로그래머스

 

---

 

#2. 풀이

 

1. DP(Dynamic Programming, 동적 계획법)

[알고리즘]#5_동적 계획법

동적 계획법은 주어진 문제의 하위 문제를 재귀적으로 해결하고, 그 결과 값을 기억하는 것으로 중복 계산을 방지하여 효율적으로 최적 해를 찾아내는 알고리즘 디자인 기법 중 하나입니다.

 

2. DP는 점화식을 세우고, 기저 조건을 먼저 설정하는 것이 중요!

1. 먼저, 원형 배열의 첫 번째 칸을 선택하는 경우, 그리고 마지막 칸을 선택하는 경우를 모두 고려해야 합니다. 일반적인 DP를 수행하는 것과 달리, 마지막 칸에 대한 경우가 첫 번째 칸의 경우의 수에 영향을 끼치기 때문입니다.
2. 그리고, 점화식을 세웁니다. 현재 칸에 대하여 이전의 결과 값들이 영향을 끼치며 이를 점화식으로 작성하면, "dp [i] = max(dp [i-1], dp [i-2]+sticker [i]), if size > 2"가 됩니다. i 칸의 경우,  i-1칸을 선택하는 경우와 i-1칸 선택 + i칸 선택의 경우를 비교하여 더 큰 값으로 설정됩니다
3. 따라서, 첫 번째 DP는 첫 번째 칸을 선택했을 경우로 시작합니다. dp1의 0번(첫 번째 칸) 과 1번(두 번째 칸) 인덱스는 모두 sticker [0]으로 기저 조건을 설정해 줍니다. 첫 번째 칸 선택 시 두 번째 칸은 자동적으로 선택 불가능하여, dp1 [1]은 sticker [0]으로 설정합니다. 
4. 그리고, 두 번째 DP는 첫 번째 칸을 선택하지 않앗을 경우로 시작합니다. dp2의 0번은 0, 그리고 1번은 sticker [1]로 기저 조건을 설정해 줍니다.
5. 마지막으로, dp1의 n-2번 인덱스의 결과 값(마지막 칸 직전 위치)과 dp2의 n-1번 인덱스의 결과 값(마지막 칸 위치)을 비교하고, 더 큰 값으로 결과 값을 출력해 줍니다.

 

---

 

#3. 코드

/*
    @링크: https://school.programmers.co.kr/learn/courses/30/lessons/12971
    @문제: 스티커 모으기(2)
    @설명
        1. DP
        2. dp[i] = max(dp[i-1], dp[i-2] + sticker[i]), if sticker.size() > 2
        3. 두 버전의 동적 프로그래밍
        - 첫 번째 항목과 마지막 항목은 연결되어 있는 순환 구조
        - 첫 번째 항목을 선택하고 진행하는 DP, 마지막 항목을 선택하고 진행하는 DP
        - 첫 번재 DP의 최종 결과 값은 dp[sticker.size()-2]에 위치하고, 두 번째 DP의 것은 dp[sticker.size()-1]에 위치.
*/
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int solution(vector<int> sticker)
{
    if(sticker.size() == 1) return sticker[0];
    if(sticker.size() == 2) return max(sticker[0], sticker[1]);
    //@첫 번째 스티커 선택
    vector<int> dp1(sticker.size(), 0);
    dp1[0] = sticker[0];
    dp1[1] = sticker[0];
    for(int i=2; i<sticker.size()-1; ++i)
    {
        dp1[i] = max(dp1[i-1], dp1[i-2] + sticker[i]);
    }
    
    //@마지막 스티커 선택
    vector<int> dp2(sticker.size(), 0);
    dp2[0] = 0;
    dp2[1] = sticker[1];
    for(int i=2; i<sticker.size(); ++i)
    {
        dp2[i] = max(dp2[i-1], dp2[i-2] + sticker[i]);
    }
    return max(dp1[sticker.size()-2], dp2[sticker.size()-1]);
}

 

---