백준18249 욱제가 풀어야 하는 문제

작성일 | In

문제 링크

  • http://icpc.me/18249

문제 출처

  • Good Bye, BOJ 2019 C번

사용 알고리즘

  • DP

풀이

정점이 $2N$개인 그래프에서 간선을 $N$개 고르는 문제이기 때문에 모든 정점이 간선의 양 끝에 포함되어야 합니다.
$D(N)$을 구해야 하는 답으로 정의하고 문제를 풀어봅시다.

  • 빨간색 1번 정점을 파란색 1번 정점과 연결하는 경우, 나머지 $2N-2$개의 정점만 적절히 연결하면 되므로 $D(N-1)$가지의 경우가 존재합니다.
  • 빨간색 1번 정점을 파란색 2번 정점과 연결하는 경우, 빨간색 2번 정점과 파란색 1번 정점이 연결되어야 하고, 나머지 $2N-4$개의 정점만 적절히 연결하면 되므로 $D(N-2)$가지의 경우가 존재합니다.

점화식은 $D(N) = D(N-1) + D(N-2)$ 이고, $D(1) = 1, D(2) = 2$이므로 191229까지 모두 전처리해주면 쉽게 풀 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;

int dp[10101010] = {1, 1};
const int mod = 1e9+7;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    for(int i=2; i<10101010; i++) dp[i] = (dp[i-1] + dp[i-2]) % mod;
    while(t--){
        int n; cin >> n;
        cout << dp[n] << "\n";
    }
}