[백준][C++] 18249: 욱제가 풀어야 하는 문제

문제 링크: https://www.acmicpc.net/problem/18249

 

Proof by ac로 풀었습니다. 무슨 말이냐면 대충 감으로 때려맞췄다는 것;

 

대충 몇 케이스를 손으로 그려보면 1, 2, 3, 5, ... 순으로 증가합니다

뭔가 피보나치같죠? dp[i] = dp[i-2] + dp[i-1]로 풀면 됩니다

..

 

그래도 증명이 좀 있어야겠죠?

n번째 케이스를 생각해보면 맨 밑 노드는 한 줄이 일자로 연결되거나, 두 줄이 X자로 연결되는 경우가 있는데 이 때 경우의 수가 n-1번째 경우와 n-2번째 경우를 더한 것과 같습니다.

Good Bye, BOJ 2019에 나온 문제인데 에디토리얼도 확인해보세요.

#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING

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


const int MOD = 1000000007;

int dp[191230];

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

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

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