[동적계획법] 스티커 모으기(2) - Summer/Winter Coding(~2018)

서로 인접한 요소를 선택하지 않으면서 합이 최댓값이 되는 요소들을 선택하는 유형의 문제다.

프로그래머즈의 도둑질 문제와 동일한 유형의 문제다. 물론 점화식도 같다.

https://kimcoder.tistory.com/92 

[동적계획법, 난이도 중상] 프로그래머즈, 도둑질

 

차이점이 있다면, 도둑질 문제는 입력 배열의 크기가 3 이상으로 정해져 있고, 이 문제는 입력 배열의 크기가 1, 2일 수도 있다는 것이다.

그래서 sticker.size() 값이 1 또는 2일 경우에 대한 처리를 해주면 된다.

점화식에 대한 설명은 도둑질 문제 포스팅을 읽고오면 된다.

 

 

소스 코드

#include <vector>
using namespace std;
int d1[100001];
int d2[100001];
int d3[100001];

int solution(vector<int> sticker)
{
    int answer = 0;
    
    // sticker의 크기가 3미만인 경우
    if(sticker.size()==1) return sticker[0];
    if(sticker.size()==2) return max(sticker[0], sticker[1]);
    
    // 1번째 스티커부터 떼는 경우
    d1[0]=sticker[0];
    d1[1]=d1[0];
    d1[2]=d1[0]+sticker[2];
    for(int i=3;i<sticker.size()-1;i++) d1[i]=max(max(d1[i-1], d1[i-2]+sticker[i]), d1[i-3]+sticker[i]);
    
    // 2번째 스티커부터 떼는 경우
    d2[1]=sticker[1];
    d2[2]=d2[1];
    for(int i=3;i<sticker.size();i++) d2[i]=max(max(d2[i-1], d2[i-2]+sticker[i]), d2[i-3]+sticker[i]);
    
    // 3번째 스티커부터 떼는 경우
    d3[2]=sticker[2];
    for(int i=3;i<sticker.size();i++) d3[i]=max(max(d3[i-1], d3[i-2]+sticker[i]), d3[i-3]+sticker[i]);

    answer=max(max(d1[sticker.size()-2], d2[sticker.size()-1]), d3[sticker.size()-1]);
    return answer;
}

 

테스트케이스 정확성, 효율성 모두 만점