[BOJ/백준][Gold2] 1670 : 정상 회담 2 (C++)

https://www.acmicpc.net/problem/1670

1670번: 정상 회담 2

 

 

 

[난이도] Gold2
[유형] DP

[풀이]
1,2,3,4,...N 순서로 동그랗게 앉아 있다고 가정했을 때,
1이 누구와 악수하는지를 고정해놓는 방식으로 풀면 DP로 답을 구할 수 있다.
예를 들어
1,4가 악수하는 경우의 수 : (2,3)이 악수하는경우의 수 * (5,6,...,N)이 악수하는 경우의 수
1,6가 악수하는 경우의 수 : (2,5)이 악수하는경우의 수 * (7,...,N)이 악수하는 경우의 수
...
...
위의 경우를 모두 더한 것이 답이다.

이것을 점화식으로 나타내면 아래와 같다.
DP[n] = DP[i] * DP[n-2-i] (0<=i<=n-2)

info) 카탈란 수라는 수학적 개념이라고 한다.

 

#include <cstdio>
#include <cstring>
using ll = long long ;
int N,mod=987654321;
ll dp[10001];
ll sol(int n){
    if(n==0||n==2) return 1;
   
    ll& ret = dp[n];
    if(ret!=-1) return ret;
    ret=0;
    for(int i=0;i<=n-2;i+=2){
        ret+=sol(i)*sol(n-2-i);
        ret%=mod;
    }
    return ret;
}
int main(){
    scanf("%d",&N);
    memset(dp,-1,sizeof(dp));
    printf("%lld",sol(N));
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold2/1670.cpp