스티커모으기2

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

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

 

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

bool check[100000]={false,};
int maxnum =0;
int dp[100000];
int dp2[100000];


int solution(vector<int> sticker)
{
    int answer = 36;
    
    if(sticker.size()==1){return sticker[0];}
     
    //dp[i] = b i번째까지의 최대값은 b 이다. 
    dp[0] = sticker[0];  
    dp[1] = sticker[0];
    
    //맨 첫번째 스티커를 선택 했을 때 (맨 뒤에꺼는 선택하지 못하니까 sticker.size()-1(끝지점 index) 의 dp 는 구하지 않는다)
    for(int i=2; i<sticker.size()-1; i++){
        dp[i] = max(dp[i-2]+sticker[i],dp[i-1]); // (현재보다 두칸 앞에 있는 곳까지의 최대값 + 현재 스티커값) vs (현재것을 선택하지 않고 이전 i-1 까지의 최대값) 
    }
    answer = dp[sticker.size()-2];
    
    dp2[0]=0;
    dp2[1]=sticker[1];
    //맨 뒤에 스티커를 선택 했을 때 (맨 앞에꺼는 선택하지 못하니까 첫번째 index의 dp값은 구하지 않는다.)
    for(int i=2; i<sticker.size(); i++){
        dp2[i] = max(dp2[i-2]+sticker[i],dp2[i-1]);// (현재보다 두칸 앞에 있는 곳까지의 최대값 + 현재 스티커값) vs (현재것을 선택하지 않고 이전 i-1 까지의 최대값) 
        
    }
    answer= max( dp[sticker.size()-2], dp2[sticker.size()-1]);
    return answer;
}

- 처음에 dp로 푸는 건지모르고 dfs로 풀다가 고민하다가 결국 풀이를 보고 dp로 푸는 것을 알게 되었다. 

중요도:  ⭐ ⭐ ⭐ ⭐