(C++) - 프로그래머스(Summer/Winter Coding(~2018)) : 스티커 모으기(2)

https://programmers.co.kr/learn/courses/30/lessons/12971

코딩테스트 연습 - 스티커 모으기(2)

 

dp문제였습니다.

 

풀이방법

 greedy하게 띄엄띄엄 최대한으로 스티커를 떼어나면 최대일 것 같으나 그렇지 않습니다. 특정한 스티커가 점수가 나머지보다 월등히 높은 경우 그 스티커를 무조건 1개씩 건너뛰면서 떼어낼 경우 그 스티커를 떼지 못할 수 있습니다. 따라서 dp를 사용해야 합니다.

 

 1. sticker의 size가 1인경우엔 바로 점수를 반환합니다.

 2. 배열 d는 다음과 같습니다. d[i] = i번 스티커를 떼어내거나 떼어내지 않았을 때 얻을 수 있는 점수의 최댓값. 이를 점화식으로 표현한다면 아래와 같습니다.

d[i] = max(d[i-2] + sticker[i], d[i-1])

즉 d[i] = max(i번째 스티커를 뜯어내는 경우, i번째 스티커를 뜯지 않는경우)입니다. i번째 스티커를 뜯어내는 경우에는 i번째의 스티커 점수를 얻을 수 있습니다. 뜯어내지 않는 경우에는 규칙에 따라 i-1번째의 점수 최댓값을 그대로 가져오게 됩니다.

 

   이 때 2가지 경우를 생각해야합니다.

   2-1. 0번 스티커를 선택했을 때

         마지막 스티커와 1번 스티커는 찢어지므로 뜯을 수 없습니다. 그러므로 d[0]과 d[1]는 sticker[0]이 됩니다. 그 후 i     는 2부터 size - 1미만까지 점화식을 따라 d를 갱신해줍니다. 그 후 마지막으로 갱신된 원소를 answer에 저장합니다.

   2-2. 1번 스티커를 선택했을 때

      0번 스티커와 2번 스티커는 뜯어낼 수 없습니다. 그러므로 d[0] = 0, d[1] = sticker[1]이 됩니다. 초기값을 갱신해준     후 i는 2부터 size미만까지 점화식을 따라 d를 갱신해줍니다. 그 후 마지막으로 갱신된 원소를 answer에 저장합니다.

 

3. answer를 반환해줍니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
 
int solution(vector<int> sticker){
    int answer = 0;
    int size = sticker.size();
    vector <int> d(size,0);
    if (size == 1) return sticker[0];
    d[0] = sticker[0];
    d[1] = sticker[0];
    for (int i = 2; i < size - 1; i++)
        d[i] = max(d[i - 2] + sticker[i], d[i - 1]);
    answer = d[size - 2];
    d[0] = 0;
    d[1] = sticker[1];
    for (int i = 2; i < size; i++)
        d[i] = max(d[i - 2] + sticker[i], d[i - 1]);
    answer = max(answer,d[size-1]);
    return answer;
}