알고리즘(C++) / 프로그래머스 level 3 : 스티커 모으기(2)

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

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

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

 

코드

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

int dp1[100001] = {0,}; //첫번째 스티커 포함
int dp2[100001] = {0,}; //첫버째 스티커 미포함

int solution(vector<int> sticker)
{
    int answer =0;
    
    //사이즈 1일 때
    if(sticker.size() == 1)
       return sticker[0]; 
    //사이즈 2일 때
    else if(sticker.size() == 2)
        return max(sticker[0], sticker[1]);
    
    //초기값
    dp1[0] = sticker[0]; dp1[1] = sticker[1];
    dp2[0] = 0; dp2[1] = sticker[1];
    answer = max(sticker[0], sticker[1]);
    dp1[2] = dp1[0] +  sticker[2];
    dp2[2] = dp2[0] +  sticker[2];
    
    for(int i=3; i<sticker.size(); i++){
        if(i != sticker.size()-1)
            dp1[i] = max(dp1[i-2], dp1[i-3]) + sticker[i];
        dp2[i] = max(dp2[i-2], dp2[i-3]) + sticker[i];
        
        //cout << dp1[i] << " " << dp2[i] << "\n";
        answer = max({answer, dp1[i], dp2[i]});
    }

    return answer;
}

 

설명

이번 문제는 DP 문제이다. 

• 첫 번째 스티커 포함하여 뜯는 dp1 배열과 첫 번째 스티거 미포함하여 뜯는 dp2배열을 나눠 문제를 풀 수 있다.
• 나누어서 푸는 이유는 N개의 스티커가 원형으로 되어있으므로 dp1배열은 마지막 스티커를 사용할 수 없도록 하여 문제를 푼다.
• 스티커의 사이즈까지 반복하여 dp1과 dp2를 반복한다. 이때 dp1은 마지막 스티커는 포함하지 않고 구한다.
• dp1과 dp2에서 가장 큰 값을 구하여 출력한다. 
• 사이즈가 1일 때와 사이즈가 2일 때는 가장 큰 값을 선택하여 출력한다. 

 

고찰

이번 문제는 스터디에서 한시간내에한 시간 내에 풀기로 했었는데 한 시간 내에 해답을 생각하지 못하여 풀지 못하였다.

처음에는 원형이라는 조건을 어떻게 하면 좋을까 고민했었는데 dp배열 두 개를 사용하면 쉽게 풀 수 있다는 것을 알 수 있었다. 다음처럼 원형이라는 조건이 있다면 두 개의 배열을 사용하여 문제를 푼다는 것을 알 수 있었다.