[알고리즘 C++] 스티커 모으기(2)

https://programmers.co.kr/learn/courses/18/lessons/1881
원형 dp는 처음 풀어본다. 첫번째 경우가 마지막에 영향을 미칠 경우에는, 첫번째가 가질 수 있는 경우에 따라 각각 나온 결과를 비교해 준다.
이 문제의 경우에는 스티커를 떼는것과 떼지 않는 경우 2가지이기 때문에 두가지 경우의 결과를 도출하여 풀었다.

오늘의 문제

스티커 모으기

나의 풀이

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

int solution(vector<int> sticker)
{
    int result;
    
    int dp[100001] = {0};
    int dp2[100001] = {0};
    
    if(sticker.size() == 1)
        return sticker[0];
    else if(sticker.size() == 2)
        return max(sticker[0], sticker[1]);
    
    // 첫번째 스티커 뜯
    dp[0] = sticker[0];
    dp[1] = sticker[0];
    for(int i=2;i<sticker.size()-1;i++)
    {
        dp[i] = max(dp[i-1], dp[i-2]+sticker[i]);
    }
    result = dp[sticker.size()-2];
    
    // 첫번째 스티커 안뜯
    dp[0] = 0;
    dp[1] = sticker[1];
    for(int i=2;i<sticker.size();i++)
    {
        dp[i] = max(dp[i-1], dp[i-2]+sticker[i]);
    }
    result = max(result, dp[sticker.size()-1]);
    
    return result;
}

모범 답안

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

int solution(vector<int> sticker)
{
	int n = sticker.size();
    if(n ==1)
    	return sticker[0];
    
    //첫 번째 스티커 뜯은 경우
    dp1[0] = sticker[0];
    dp1[1] = dp[0];
    for(int i=2;i<n-1;i++)
    	dp1[i] = max(dp1[i-1], dp[i-2] +sticker[i]);
    //첫 번째 스티커 뜯지 않은 경우
    dp2[0] = 0;
    dp2[1] = sticker[1];
    for(int i=2;i<n;i++)
    	dp2[i] = max(dp2[i-1], dp2[i-2]+sticker[i]);
    return max(dp1[n-2], dp2[n]);
}

배울 점

• 모범답안에서 n 을 선언하듯 하자. 꼭 길이가지고 지저분하게 쓰지 말자