백준 1904 - 01타일

문제

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

1904번: 01타일

 

풀이

길이가 N인 수를 만드는 개수를 구하는 문제이다. 사용할 수 있는 숫자는 00이랑 1이다. 즉 전에 만들었던 숫자에 00이나 1을 붙여서 현재 수를 만들면 된다. 근데 00은 N-1번째에서 붙일 수 없고 N-2번째에서 붙여야 한다. 1은 N-1번째에서 붙이면 된다. 따라서 N번째에서 가능한 숫자의 수는 (N-2번째 숫자들 + 00타일), (N-1번째 숫자들 + 1타일)이된다. 그런데 숫자 타일만 붙이는 것이므로 N-2번째와 N-1번째의 가능한 숫자의 수는 변하지 않는다. 

따라서 N번째 가능한 숫자의 수는 (N-1번째의 숫자들) + (N-2번째의 숫자들)이 된다.

 

코드

#include <iostream>
 
using namespace std;
 
int N;
int dp[1000001];
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> N;
 
    dp[1] = 1;
    dp[2] = 2;
 
    // i-1에선 1을 붙이고, i-2에선 00을 붙인다
    for (int i = 3; i <= N; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
        dp[i] %= 15746;
    }
 
    cout << dp[N];
 
    return 0;
}