스티커 모으기

출처-프로그래머스

1. 알고리즘

• 동적계획법

2. 문제 풀이

가장 기본적인 방법은 모든 경우를 다 따지는 것이다.
그런데 원소의 개수가 최대 100,000개이기 때문에 상상할 수 없을 만큼 오래걸린다.
따라서 경우의 수를 최대한 줄여줘야 하는데, 그 중 첫번째로 탐욕법을 생각해봤다.

2-1. 탐욕법

탐욕법은 매 순간 최적의 선택을 해야한다.
그런데 이 문제에서는 최적의 선택이 상당히 모호하다.

1. 매번 최대 숫자를 선택하기에는 그게 최대합이라는 보장이 없다.
   반례로 위 그림의 경우에는 14를 포기하고 10, 6, 11, 9를 선택해야 최대 합을 얻을 수 있다.

2. 뜯으려는 스티커의 값과 양옆의 뜯기게 될 스티커의 합을 비교하여 뜯는 방법도 생각해 봤으나
   여전히 이게 최대합이라는 보증을 할 수가 없었다.

그래서 경우의 수를 줄이기 위한 또 다른 알고리즘 기법을 생각했다.

2-2. 다이나믹 프로그래밍

• 다이나믹 프로그래밍의 기본은 아래 2가지다.

  1. 작은 문제로 분할하기.
  2. 작은 문제의 답을 기록해서 재사용하기.

따라서 우선 n개의 스티커를 1개, 2개, 3개, 4개, .... 순차적으로 답을 구해보기로 했다.
즉 n개의 스티커를 마지막 한 개와 나머지 n-1개, n-1개의 스티커를 마지막 한 개와 n-2개, ... 이와 같이 작은 문제로 쪼개서 1개부터 합쳐나가는 것이다.

그 결과, sum[i] = max(sum[i-2], sum[i-3]) + sticker[i] 의 식을 구할 수 있었다.

• 위 식에서 sum[i]는 0~i 스티커 중에서 스티커를 뜯을 때의 최대합이다. 단, i는 반드시 뜯어야 한다.
• sum[0], sum[1]은 초기값으로 설정해 줘야한다.

그런데 위 식에는 한 가지 복병이 있다.

총 0 ~ n-1의 n개의 스티커가 있다고 하자.
sum[n-1]을 구할 때, sum[n-3]과 sum[n-4]에 sticker[0]이 포함되어 있는지 알 수 없다는 것이다.
(0번째 스티커를 미리 뜯었다면, n-1번째 스티커가 같이 뜯긴다.)

따라서 경우를 2가지로 나눠야만 했다.

1. 0번 스티커를 뜯고 시작한다.
2. 1번 스티커를 뜯고 시작한다.

위 두가지 경우에 대해서 각각 최대합을 구한 뒤,
다시 그 두개 중 최대합을 구했다.

(코드에선 sum 대신 memo를 배열명으로 사용했다.)

소스코드

#include <vector>
using namespace std;

int maxNum(int a, int b)
{
    return (a>b) ? a : b;
}

int solution(vector<int> sticker)
{
    int answer = 0;
    int len = (int)sticker.size();
    
    // 작은 문제 답 기록
    vector<int> memo(len, 0);
    
    // 0번째 스티커 뜯음
    memo[0] = sticker[0];
    answer = memo[0];
    
    for (int i = 2; i < len - 1; i++)
    {
        if (i-3 < 0)
            memo[i] = memo[i-2] + sticker[i];
        else
            memo[i] = maxNum(memo[i-2], memo[i-3]) + sticker[i];
        
        // 최댓값 갱신
        if (answer < memo[i])
        {
            answer = memo[i];
        }
    }
    
    for (int i = 0; i < len; i++)
        memo[i] = 0;
    
    
    if (len == 1)
        return answer;
    
    // 1번째 스티커 뜯음.
    memo[1] = sticker[1];
    
    if (answer < memo[1])
        answer = memo[1];
    
    for (int i = 2; i < len; i++)
    {
        if (i-3 < 0)
            memo[i] = memo[i-2] + sticker[i];
        else
            memo[i] = maxNum(memo[i-2], memo[i-3]) + sticker[i];
		
        // 최댓값 갱신
        if (answer < memo[i])
        {
            answer = memo[i];
        }
    }
    
    return answer;
}