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

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/12971

Key

처음 원소를 선택했을 경우의 dp배열, 두번째 원소를 선택했을 경우의 dp배열 두가지 배열의 마지막 원소를 비교하여 최댓값을 구하는 문제이다.

또한 해당 원소를 골랐을 때의 최댓값을 구하는 방법은, 인접한 것을 고르지 못하므로 i-1번 까지의 최댓값과, i-2번까지의 최댓값 + 해당 원소의 값을 비교하여 둘 중 큰 것으로 골라야 한다.

만약 dp를 하나만 만든다고 가정해보자.

예시와 같이 14, 6, 5, 11, 3, 9, 2, 10 가 주어졌을 때, 점화식으로 현재 원소까지의 최댓값을 구하면 다음과 같다.

수	14	6	5	11	3	9	2	10
현재까지의 최댓값	14	14	19	25	25	34	34	44

따라서 구할 수 있는 가장 큰 값은 44라고 하면 오답이다.

지금 이 dp배열로 인접하지 않게 구할 수 있는 최댓값을 구할 수는 있지만, 처음과 끝에도 인접할 수 있다는 사실을 간과하게 된다. 따라서 맨 앞 원소(14)를 고르면, 맨 뒤 원소(10)을 고르면 안된다.

따라서 다음과 같이 1)맨 앞 원소를 고르는 경우 2)맨 뒤 원소를 고르는 경우 두가지로 나누어 최댓값을 구해야한다.

수	14	6	5	11	3	9	2	10
1)	14	14	19	25	25	34	34	34
2)	-	6	6	17	17	26	26	36

구하고자 하는 값은 dp의 마지막 원소 두개 의 값 중 최대값이 된다.

 

Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//동적계획법 dp를 두개 만들자 
//1)처음 원소를 선택했을 때의 dp배열
//2)두번째 원소를 선택했을 때의 dp 배열
const int MAX = 100001;
int dp_1[MAX];
int dp_2[MAX];
int solution(vector<int> sticker)
{
    int answer = 0;
    //처음 원소 선택
    dp_1[0] = sticker[0];
    dp_1[1] = sticker[0];
    
    //dp_1에 대해
    for(int i=2;i<sticker.size();i++){
        if(i == sticker.size()-1){ //마지막 dp의 경우 그 전의 dp와 같다(선택하지 못하므로)
            dp_1[i] = dp_1[i-1];
            break;
        }
        dp_1[i] = max(dp_1[i-1],dp_1[i-2] + sticker[i]);
    }
    
    
    //두번째 원소 선택
    dp_2[0] = 0;
    dp_2[1] = sticker[1];
    
    //dp_2에 대해
    for(int i=2;i<sticker.size();i++){
        dp_2[i] = max(dp_2[i-1],dp_2[i-2] + sticker[i]);
    }
 
    answer = max(dp_1[sticker.size()-1],dp_2[sticker.size()-1]);
    return answer;
}