백준 #11726

2×n 타일링 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

103673

39161

28643

35.504%

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1 복사

2

예제 출력 1 복사

2

예제 입력 2 복사

9

예제 출력 2 복사

55

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 다이나믹 프로그래밍

 

 

 

 

 

---

흰색이 가로 사각형, 검은색이 세로 사각형이라고 가정하면

 

1   
□□

2   
□□  ■■    
□□  ■■

3  
□□ ■■ □□
□□ ■■ ■■ 
□□ □□ ■■ 

4
□□ ■■ □□ □□ ■■
□□ ■■ ■■ □□ ■■
□□ □□ ■■ ■■ ■■
□□ □□ □□ ■■ ■■

5
□□ ■■ □□ □□ □□ ■■ ■■ □□
□□ ■■ ■■ □□ □□ ■■ ■■ ■■
□□ □□ ■■ ■■ □□ ■■ □□ ■■
□□ □□ □□ ■■ ■■ ■■ ■■ ■■
□□ □□ □□ □□ ■■ □□ ■■ ■■

 

 

 

 

 

크기를 살펴보면 1 2 3 5 8 처럼 피보나치 수열과 같은 숫자가 나온다. 출력에 10,007로 나눠서 나머지를 출력하라고 했으므로 아래 코드를 제출하면 문제가 해결된다.

 

import sys

if __name__ == '__main__':

    N = int(sys.stdin.readline())
    dp = [0 for i in range(1001)]

    dp[1] = 1
    dp[2] = 2

    for i in range(3, N+1):
        dp[i] = dp[i-1] + dp[i-2]

    print(dp[N] % 10007)