[Algorithm] Programmers :: 스티커 모으기(2)

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

프로그래머스

int dp[100001] = { 0 };
 
int solution(vector<int> sticker)
{
    int answer = 0;
 
    if (sticker.size() == 1) return sticker[0];
    dp[0] = sticker[0];
    dp[1] = sticker[0];
 
    for (int i = 2; i < sticker.size() - 1; ++i)
    {
        dp[i] = max(dp[i - 2] + sticker[i], dp[i - 1]);
    }
    answer = dp[sticker.size() - 2];
 
    memset(dp, 0, sizeof(dp));
 
    dp[0] = 0;
    dp[1] = sticker[1];
 
    for (int i = 2; i < sticker.size(); ++i)
    {
        dp[i] = max(dp[i - 2] + sticker[i], dp[i - 1]);
    }
 
    answer = max(answer, dp[sticker.size() - 1]);
    return answer;
}

일단 dp문제인건 알았고, 현재 인덱스에서 +2,+3지점을 두고 선택하거나 안선택하면서 업데이트하는건줄 알았는데... 접근은 뭔가 맞는가싶었지만 그게 정답에 도달 안해서 다른사람 풀이를 봤더니 다른 점화식이였다...

일단 dp[i]는 0부터 i까지의 최대값이다.

 

큰 틀은 첫번째랑 두번째 스티커를 각각 선택했을 때의 경우를 구분해서 두 경우중 더 큰값을 리턴하면 되는것이다.

만약 첫번쨰 스티커를 찢었다면 dp[0]에 sticker[0]값을 넣어주게 될텐데, 이 때 dp[0]뿐만 아니라 dp[1]에도 같은 sticker[0]값을 넣어준다. 어차피 0번째 스티커를 찢었기 때문에 1번째는 못찢는다. 그렇기 때문에 sticker[0]번값으로 갱신해주는 것이다.

dp 0번과 1번값을 갱신하고, 반복문을 2부터 sticker.size()-1까지 진행할 것이다. 왜 -1이 있냐면, 0번째를 찢었기 때문에 바로 왼쪽인 끝인덱스는 건드리지 못하기 때문이다.

그렇기때문에 끝인덱스-1번째의 스티커까지만 건드릴 수 있다.

점화식은 dp[i] = max(dp[i-2] + sticker[i], dp[i-1]) 인데, dp[i-2] + sticker[i]는 현재 인덱스의 스티커를 찢은것을 의미하고 dp[i-1]은 안찢고 넘어갔다는 걸 의미한다. 그렇기 때문에 두 값중 큰값으로 갱신해준다.

 

이후 비슷한 원리로 0번째 스티커를 안찢은 루트에 대해 최대값을 구해준다.

0번째를 안찢었기 때문에 dp[0]에는 0을 넣어주고, 0번째를 안찢고 1번째를 찢었기 때문에 dp[1]에 sticker[1]값을 넣어주고 dp갱신을 수행한다. 점화식은 당연히 똑같고, 이후 두 루트값 중 큰값을 리턴하면 된다.