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)); }