BOJ 1904 - 01 타일

문제

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

풀이

1과 00만을 이용한 길이가 N인 이진 수열이 몇개인지 찾는 문제이다. 1과 00만을 사용해야 해야하므로 0이 혼자 쓰여서는 안된다. 이 문제는 직접 몇 개의 케이스를 손으로 적어서 풀었다.

DP[1] = 1

DP[2] = 11, 00

DP[3] = 111, 100, 001

DP[4] = 1111, 1100, 1001, 0011, 0000

DP[5] = 11111, 11001, 10011, 10000, 00001, 00100, 00111, 01001

...

길이가 N일때의 갯수를 세어보면 $ DP[N] = DP[N-1] + DP[N-2] $, 즉 이 문제는 단순한 N번째 피보나치 수를 구하는 문제와 같다.

#include <stdio.h>
int dp[1000001];
int solve(int x){
	if(dp[x]) return dp[x];
	return dp[x] = (solve(x-1) + solve(x-2)) % 15746;
}
int main() {
	int n;
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 3;
	scanf("%d",&n);
	printf("%d",solve(n));
}