문제

문제 링크

해설

• 00 또는 1 타일만 사용할 수 있는 상황입니다.
• DP[N]을 N개의 타일을 놓을 수 있는 최대 경우의 수라고 정의합시다.
  • N - 2개의 타일을 놓았을 때, 00 타일을 놓는다면, N개의 타일을 놓을 수 있습니다.
  • N - 1개의 타일을 놓았을 때, 1 타일을 놓는다면, N개의 타일을 놓을 수 있습니다.
  • 즉, DP[N]은 DP[N - 2] + DP[N - 1]라는 점화식으로 나타낼 수 있습니다.
• 이때, 문제 조건에 따라 15,746으로 나눈 나머지를 구해야하므로, 매 점화식 계산마다 해당 상수로 모듈라연산을 수행합니다.

코드

#include <bits/stdc++.h>
using namespace std;
constexpr int MOD = 15'746;

int N, DP[1'000'001];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	cin >> N;
	
	DP[1] = 1; DP[2] = 2;
	for (int i = 3; i <= N; ++i) DP[i] = (DP[i - 2] + DP[i - 1]) % MOD;
	
	cout << DP[N];
}

소스코드 링크

결과