[2302] 극장 좌석

http://boj.kr/2302

d[n] : VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수

- 소스코드

#include <stdio.h>
 
int vip[41], d[41];
 
int go(int k)
{
    int ret;
    if(k == 0 || k == 1) return 1; 
    if(d[k]) return d[k];
    if(vip[k]) return d[k] = go(k-1);
 
    ret = go(k-1);
    if(!vip[k-1]) ret += go(k-2);
    
    return d[k] = ret;
}
 
int main()
{
    int n, m, k;
    scanf("%d%d", &n, &m);
 
    while(m--) {
        scanf("%d", &k);
        vip[k] = 1;
    }
 
    printf("%d\n", go(n));
    return 0;
}

>> n이 n번에 앉았을 때의 경우의 수 : d[n-1] 

>> n이 n-1에 앉았을 때의 경우의 수 : d[n-2]

>> 여기서는 10번 라인을 쓰지 않으면, n-1번이 vip석이 아닌경우 n번이 vip석이여도 n-1과 n번이 

     바꿔 앉는 경우를 세어 중복이 발생한다.