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

출처 : programmers.co.kr/learn/courses/30/lessons/12971

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

 

고려사항

• 백준에서 아주 비슷한 문제를 풀었었다.
• 첫 원소를 사용한 경우와 ( memo[1][0] ~ memo[1][len-1] )
  첫 원소를 사용 안 한 경우로 나눈다 ( memo[0][0] ~ memo[0][len-1] )
• 첫 원소를 사용 했다면! 최댓값은 memo[1][len-2] 에 위치한다.
  첫 원소를 사용 안했다면 최댓값은 memo[0][len-1] 에 위치한다.
• 점화식은 dp[isFirst][idx] = max( dp[isFirst][idx-2] + sticker[idx], dp[isFirst][idx-1] ) 이다.
  문제 조건에서 서로 인접한 수는 사용할 수 없으니!
• 재귀의 base를 잘 설정해준다.
  isFirst == 1 이면, dp[1][0] = sticker[0], dp[1][1] = sticker[0] ( 첫 원소를 썼다! 고로 2번째 원소는 못 쓴다! )
  isFirst == 0 이면, dp[0][0] = 0, dp[0][1] = sticker[1] ( 첫 원소를 안 썼다! 고로 2번째 원소를 쓴다! )

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
using namespace std;
 
int memo[2][100000];
 
int dp(vector<int> &sticker, int idx, int isFirst){
    int &v = memo[isFirst][idx];
    
    if(v != -1){
        return v;
    }
    
    v = max(dp(sticker, idx-2, isFirst)+sticker[idx], dp(sticker, idx-1, isFirst));
    
    return v;
}
 
int solution(vector<int> sticker)
{
    int answer = 0;
    int len = sticker.size();
    
    if(len == 1){
        answer = sticker[0];
        return answer;
    }
    
    memset(memo[0], -1, 4*len);
    memset(memo[1], -1, 4*len);
    memo[1][0] = sticker[0];
    memo[1][1] = sticker[0];
    memo[0][0] = 0;
    memo[0][1] = sticker[1];
    
    answer = max(dp(sticker, len-1, 0), dp(sticker, len-2, 1));
 
    return answer;
}