[Silver II] 욱제가 풀어야 하는 문제 - 1829

 

[문제 위치]

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

[문제 풀이]

강 i와 파랑 i를 잇는 “세로”와 양옆을 살짝 비껴 잇는 “대각”이 만들어내는 그래프는 2×N의 연속된 K_{2,2} 사슬이 된다. 완전 매칭을 왼쪽에서 오른쪽으로 채우면, 맨 오른쪽 빨강 N이 선택할 수 있는 건 파랑 N 또는 파랑 N−1뿐이고, 파랑 N−1을 고르면 N−1과 N이 서로 스왑으로 고정되며 왼쪽 N−2 구간만 남는다. 그래서 f(N)=f(N−1)+f(N−2), 초기값 f(1)=1, f(2)=2, 즉 답은 Fibonacci의 F_{N+1}가 된다.

 

아래는 이를 구현한 것이다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    const int MOD = 1000000007;
    int T;
    if(!(cin >> T)) return 0;
    vector<int> N(T);
    int mx = 0;
    for (int i = 0; i < T; ++i) {
        cin >> N[i];
        mx = max(mx, N[i]);
    }
    // fib[0]=0, fib[1]=1, 정답은 fib[N+1]
    vector<int> fib(mx + 2 + 1, 0);
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i <= mx + 1; ++i) {
        fib[i] = (fib[i-1] + fib[i-2]) % MOD;
    }
    for (int n : N) {
        cout << fib[n + 1] << '\n';
    }
    return 0;
}