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

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

아이디어

문제에서 말한 그래프를 그려보자

N = 4

문제의 요구사항에 맞춰 N개의 간선을 직접 선택하다 보면 다음 사실을 발견할 수 있다.

 

그래프를 위 그림처럼 보고 평행한 두 정점을 한 줄이라 취급했을 때 N개의 간선을 선택하면 N번째 줄까지 도달한 상태여야 한다.

 

즉 N개의 간선을 선택하는 방법은 N번째 줄에 도달하는 방법과 동치이며 한 줄을 잇는 한 줄 간선이나 4개의 정점을 교차하여 잇는 쌍칼 간선을 적절히 선택하여 N번째 줄에 도달하는 방법을 생각하면 된다.

 

쌍칼이 아니라 대각선 간선으로만 배치하는 경우 N개의 간선을 선택할 수 없다.

 

우리는 이 발견으로 다음 점화식을 세울 수 있다.

 

$f(n) = f(n - 1) + f(n - 2) \; (f(1) = 1, f(2) = 2)$

 

세운 점화식을 DP로 구현하고 쿼리에 맞는 답을 출력하면 된다.

 

전체 코드

#include <bits/stdc++.h>

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define mod 1000000007

using namespace std;
using pii = pair<int, int>;
using ll = long long;

int t;
ll dp[191230];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= 191229; ++i)
        dp[i] = (dp[i - 1] + dp[i - 2]) % mod;

    cin >> t;

    while (t--)
    {
        int q;
        cin >> q;
        cout << dp[q] << '\n';
    }
}