프로그래머스 - 스티커 모으기(2) [C++]

 이 문제는 프로그래머스 level 3 문제이다. 이 문제를 처음에는 백트래킹을 이용해서 풀었으나, 당연히 시간 초과가 났다. dp를 이용해서 푸는 문제임을 알았지만, 방법을 떠올리지 못했다.

 이 문제는 dp 배열을 i번째 스티커까지 왔을 때 최댓값으로 생각하면 풀 수 있다. 여기서 중요한 것은 0번째 스티커를 뜯으면 마지막 스티커를 뜯을 수 없고, 1번째 스티커를 뜯으면 마지막 스티커를 뜯을 수 있다는 것이다. 따라서 루프를 두번 돌려 값을 비교한 뒤 최댓값을 출력하면 된다.

 

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int dp[100001];

int solution(vector<int> sticker)
{
    int answer = 0;
    
    int N = sticker.size();

    if (sticker.size() == 1) {
        return sticker[0];
    }
    
    dp[0] = sticker[0];
    dp[1] = sticker[0];
    
    // 0번 뜯음 - N-1번 못 뜯음
    for (int i = 2; i <= N - 2; i++) {
        dp[i] = max(dp[i - 2] + sticker[i], dp[i - 1]);
    }
    
    answer = max(answer, dp[N - 2]);
    
    // 0번 안뜯음 - N - 1 번 뜯을 수 있음
    dp[0] = 0;
    dp[1] = sticker[1];
    for (int i = 2; i <= N - 1; i++) {
        dp[i] = max(dp[i - 2] + sticker[i], dp[i - 1]);
    }
    answer = max(answer, dp[N - 1]);
    
    return answer;
}