백준 11726 (2×n 타일링)

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

point

dp를 활용해 푸는 문제이다. 근데 더 중요한 부분은 overflow이다.
나머지를 출력하는데 n이 1000까지 올 때 오버플로우가 발생할 수 있다. 따라서 배열에 값을 넣을 때부터 이미 나머지 값을 넣어줘야 한다.

code

#include <bits/stdc++.h>
using namespace std;
int n;
int tile[1002];

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(0);

    cin >> n;
    tile[1] = 1;
    tile[2] = 2;
    for (int i = 3; i <= n; i++)
        tile[i] = (tile[i - 1] + tile[i - 2]) % 10007;
    
    cout << tile[n];
    return (0);
}