[C++] 1904 - 01타일

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

1904번: 01타일

 

 

이 문제를 풀면 피보나치 수열이 정답이라는것을 알게 된다.

내가 생각하는 이유를 적어보자면 먼저 우리는 타일을 두 가지 가지고 있다. '00'과 '1'.

 

따라서 내가 '00'을 마지막으로 붙이면서 n자리를 만족하기 위해서는

n-2의 길이에 더해서 만들 수 있기 때문에

'00' 타일 : dp[n] += dp[n-2] 

 

그리고 '1'을 붙이면서 n자리를 만족하기 위해서는 n-1길이에 더해서 만들 수 있기 때문에

'1' 타일 : dp[n] += dp[n-1]

 

따라서 최종적으로 dp[n] = dp[n-1] + dp[n-2]이라는 점화식이 완성되고 이는 피보나치와 같게 된다.

 

#include<iostream>
#include<algorithm>
#include<map>
#include<utility>
#include<vector>
 
using namespace std;
 
int main(void)
{
    int n;
    
    int x = 1, y = 1;
    int tmp;
    cin >> n;
 
    while(n--)
    {
        tmp = x+y;
        x = y;
        y = tmp%15746;
    }
 
    cout << x << endl;    
    return 0;
}