[BOJ/C++]11726번 2xn 타일링

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

11726번: 2×n 타일링

dp를 이해하고 나니 한결 쉽게 풀 수 있었던 문제.

바보같이 10007의 나머지를 구하라는 조건을 못 보고 계속 틀렸습니다 나와서 열났던 문제이다.

 

문제

사용자로부터 n을 입력받고, 2xn크기의 직사각형을 만든다. 이 직사각형에는 2x1또는 1x2타일이 들어갈 수 있다.

2xn 크기의 직사각형에 타일이 들어가는 경우의수를 구해라.

 

풀이방법

이 문제는 점화식으로 풀 수 있다.

2x1과 1x2의 타일은 i번째 직사각형에서 다음과 같이 두 가지 경우로 들어갈수 있다.

따라서 i번째에서는 i-1번째까지의 타일의 경우의 수와 i-2번째 가지의 타일의 경우의 수를 더하면 된다.

 

 

소스코드

#include<iostream>
using namespace std;

int main(void){
    int n;cin>>n;
    int dp[n+1];
    dp[1]=1;dp[2]=2;
    for(int i=3;i<=n;i++)
        dp[i]=(dp[i-1]+dp[i-2])%10007;//왜 10007로 나누라고 할까?-괄호 안해서 계속 틀렸음 이런..
    cout<<dp[n]<<endl;
}

내 생각에 10007로 나누라고 조건을 건 이유는 커졌을 때 피보나치 수열이라 너무 커지면 int형으로 출력이 안 돼서 오류가 나기 때문이지 않을까..싶다.