[파이썬] 11726번 : 2×n 타일링

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

11726번: 2×n 타일링

문제

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

 

생각

일단 규칙을 찾아보고자 나열해서 몇번에 해당하는 방법이 있나 살펴봐보자라고 접근하였다.

'''
n = 1   n = 2   n = 3   n= 4     n=5                                                                                
1번       2번      3번     5번     8번                                         
                n=2     n=2
                
ㅣ       ㅣㅣ   ㅣㅣㅣ   ㅣㅣㅣㅣ    ㅣㅣㅣㅣㅣ
         ==     ==ㅣ   ㅣㅣ ==    ㅣㅣㅣ ==
               ㅣ==    ㅣ == ㅣ    ㅣㅣ==ㅣ
                       == ㅣ ㅣ    ㅣ==ㅣㅣ
                       == ==       ==ㅣㅣㅣ
                                   == == ㅣ
                                   ==ㅣ==
                                  ㅣ == ==
                                
'''

위와 같이 되는데 n=3일때부터 n=1과 n=2를 합한결과, n=4일때는 n=2과 n=3을 합한결과라는 것을 알게 되었다 이것을 코드로 옮기면 된다.

-> 동적계획법이구나 그러면 Bottom-up방식을 쓰자!

import sys
n=int(sys.stdin.readline())

tile_count_list=[0 for _ in range(1001)]
tile_count_list[0]=0
tile_count_list[1]=1
tile_count_list[2]=2
for i in range(3,1001):
    tile_count_list[i]=tile_count_list[i-1]+tile_count_list[i-2]

print(tile_count_list[n]%10007)

나는 맨처음에 1001에 해당하는 것을 설정하지 않고 입력받은 n을 가지고 했었는데 indexError가 떴었다.

왜냐하면 n이 1이 들어갈경우에 2에 대한 인덱스가 없었기 때문이다. 이런 것을 조금 조심해야겠다.

밑이 처음에 작성한 코드이다.

import sys
n=int(sys.stdin.readline())

def tile_count(a):
    tile_count_list=[0 for _ in range(a+1)]
    tile_count_list[0]=0
    tile_count_list[1]=1
    tile_count_list[2]=2 //a가 1이들어올 경우 indexerror가 뜬다.
    for i in range(3,a+1):
        tile_count_list[i]=tile_count_list[i-1]+tile_count_list[i-2]
    return tile_count_list[a]

print(tile_count(n)%10007)