# 백준 : 01타일(1904)

문제

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

소스

(Github: https://github.com/wonjnlee/wallydev/blob/master/bj_1904_01tile)

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <list>
using namespace std;

#define MAX 1000000

long long int dp[MAX + 1] = {0,};

int main(void)
{
    long long int value;
    cin>>value;
    
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    
    for(int i=3; i<=value; i++) {
        dp[i] = dp[i - 2] + dp[i - 1];
        dp[i] %= 15746;
    }
    cout<<dp[value]<<endl;
    return 0;
}

풀이

전형적인 피보나치문제. DP를 이용해서 계산과정을 빠르게 할 뿐이다.
문제에서 이야기하는 N이 1000000이 되면, 당연히 계산속도가 어마어마하게 느려지게 되므로 DP를 사용해서 쉽게 계산할 수 있게 된다.
이 문제에서 '그나마' 까다로운 부분은 나머지 연산을 마지막에 해줘야 한다는 점.
마지막에 나머지연산을 하게되면 어차피 오버플로우된 값이 나머지 연산을 진행하므로 원하는 답을 출력하지 못하기 때문에, DP계산을 하는 과정에서 계속 나머지 연산을 진행해주면 된다.