프로그래머스 : 스티커 모으기(2)

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

프로그래머스

 

어렵닷...!!!

dp로 푸는 문제였다.

 

처음에는 dfs로 풀었는데 (어제 풀었던 상담 문제처럼,,) 시간초과 때문에 다시 고민했다.

 

스티커가 원형으로 이어져 있기 때문에, [0]이랑 [마지막] 을 주의깊게 봐줘야 한다.

 

case1 : [0]을 무조건 뜯는상황 == [마지막]은 찢어져서 절대 사용 못함

=> 즉, [0] .... [마지막-1] 이라는 배열에서 최고값을 찾는 문제와 똑같아진다 (이 상황에서는 원형을 생각하지 않아도됨)

case2 : [0]을 무조건 안뜯는 상황 == [마지막]을 고려할 수 있음

=> 즉 [1] ... [마지막] 이라는 배열에서 최고값을 찾는 문제와 똑같아진다 (이 상황에서는 원형을 생각하지 않아도 됨)

 

그러면 어떠한 배열이 있을 때(원형X), 여기서 뜯었을 때 최고값이 나오도록 하는 문제는 어떻게 풀어야 할까?

dp[i] = max( [i]스티커를 뜯었을 때, [i]를 안뜯었을 때 ) 로 생각하면 된다.

 

[2, 5, 11, 3] 이라는 스티커 배열을 생각해보자.

dp[0] : 뜯었을때는 2, 안뜯었을때는 0이므로, => 2

dp[1] : 뜯었을때는 5, 안뜯었을때는 2 ([0]을 뜯어야함!) => 5

dp[2] : 뜯었을때는, 11+2 = 13, 안뜯었을때는 5 => 13

dp[3] : 뜯었을때는, 3 + 5 = 8,  안뜯었을때는 13 => 13

...

 

규칙은

i == 0

    dp[i] = sticker[i]

i == 1

    dp[i] = max(dp[i-1], sticker[i])

else

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

                      dp[i-1] : 안뜯을때

                      dp[i-2] + sticker[i] : 뜯을 때

로 정리할 수 있다.

 

---

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> sticker)
{
    int answer =0;
    
    if(sticker.size() == 1){
        return sticker[0];
    }else if(sticker.size() == 2){
        return max(sticker[0], sticker[1]);
    }

    // [0]을 부조건 뜯는경우
    vector<int> case1 = sticker;
    case1.pop_back();
    vector<int> dp1(case1.size(), case1[0]);
    for(int i = 2; i<case1.size(); i++){
        dp1[i] = max(dp1[i-1], dp1[i-2] + case1[i]);
    }
    
    // [0]을 안뜯는 경우
    vector<int> case2(sticker.begin()+1, sticker.end());
    vector<int> dp2(case2.size(), case2[0]);
    dp2[1] = max(dp2[0], case2[1]);
    for(int i = 2; i<case2.size(); i++){
        dp2[i] = max(dp2[i-1], dp2[i-2] + case2[i]);
    }
    
    answer = max(dp1[dp1.size()-1], dp2[dp2.size()-1]);
    
    return answer;
}

 

vector를 인자로 받는 함수를 만들어서 작성하는게 보기에는 깔끔했을것 같은데

경우의 수가 2개밖에 없어서 그냥 그대로 썼다!