[C/C++] Lv4 프로그래머스 - 스티커모으기(2)

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

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

- 접근법

 

사실 이 문제는 간단한 원형 다이나믹 문제이다.

처음 인덱스의 정보가 마지막 인덱스의 정보에 영향을 끼친다는 것을 배제하고 문제를 다시보면

"연속하지 않는 숫자들의 최대합" 으로 볼 수 있고 여기에 처음 인덱스의 숫자를 선택했을 때와 선택하지 않았을 때 중 큰 값이 문제의 정답이 된다.

따라서 "연속하지 않는 숫자들의 최대합"은 1차원 배열의 DP로 쉽게 생각해볼 수 있다.

점화식을 간단히 생각해보면 Dy[i]= ( Dy[i-2]+현재숫자 , Dy[i-1] ) 중 큰 값 으로 생각해볼 수 있다.

그리고 다시 배제하였던 원형 다이나믹을 고려해본다면 처음 인덱스의 숫자를 선택했다면 Dy 배열에 정답은 Dy[N-2]에 있을 것이고 처음 인덱스의 숫자를 선택하지 않았다면 정답은 Dy[N-1]에 있을 것이다. (N-1은 인덱스가 0부터 시작하므로)

---

- 유사문제

www.acmicpc.net/problem/17404

17404번: RGB거리 2

대표적인 원형다이나믹 문제.

단 각 인덱스에서 선택할 수 있는 옵션이 3가지있다는 점이 차이점이다.

 

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

코딩테스트 연습 - 도둑질

이 문제와 100% 같다고 볼 수 있다.

---

-소스코드

#include <iostream>
#include <vector>
using namespace std;
#define MAXI(A,B) A>B ? A : B
int Dy[100010];
int N;
int re(int idx) {
    if(idx<0) return 100002;
    return idx;
}
int Dynamic(int picked,vector<int> sticker) {
    Dy[0]=picked;
    for(int i=1;i<N;i++) {
        Dy[i]=MAXI(Dy[i-1],Dy[re(i-2)]+sticker[i]);
    }
    if(picked==0) return Dy[N-1];
    return Dy[N-2];
}
int solution(vector<int> sticker)
{
    int answer = 0;
    N=sticker.size();
    if(N==1) return sticker[0];
    answer=Dynamic(sticker[0],sticker);
    answer=MAXI(answer,Dynamic(0,sticker));
    return answer;
}