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

문제

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

프로그래머스

 

원형 배열에서 스티커의 최대 합을 구하는 문제였다.

 

문제 풀이

dp를 이용해 풀었다. 첫 번째 스티커를 뜯는 경우와 뜯지 않는 경우를 나눠 dp를 구하고 max 값을 구했다. N이 1부터 시작인 것을 놓치고 sticker 배열의 size가 1,2인 경우에 예외처리를 해주지 않아서 2개 정도의 테케가 틀렸다고 나왔었다.

 

주어진 입력값의 범위를 항상 주의해서 보자!

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

int solution(vector<int> sticker)
{
    vector<int> dp(sticker.size());
    int maxSum = -1;
    int i;
    int answer = 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] = dp[0];
    for(i=2;i<sticker.size()-1;i++){ //마지막 스티커 뜯지 못함
        dp[i] = max(dp[i-1], dp[i-2]+sticker[i]);
    }
    dp[i] = dp[i-1]; //마지막 스티커 안뜯음    
    maxSum = max(maxSum, dp[i]);
    
    //첫 번째 스티커 안 뜯을 경우
    dp[0] = 0;
    dp[1] = sticker[1];
    for(i=2;i<sticker.size();i++){ //마지막 스티커 뜯을 수 있음
        dp[i] = max(dp[i-1], dp[i-2]+sticker[i]);        
    }
    maxSum = max(maxSum, dp[i-1]);
    
    answer = maxSum;
    return answer;
}