[모각코] 210825 Today I Learned

HUFS/2021 HUFS 모각코 캠프

[모각코] 210825 Today I Learned

sohy 2021. 8. 27. 01:27

11726번: 2×n 타일링

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

www.acmicpc.net

n = int(input())
C = [0 for i in range(n+1)]  # 방법의 수

for i in range(1, n+1):
    if i == 1:
        C[i] = 1
    elif i == 2:
        C[i] = 2
    else:
        C[i] = C[i-1] + C[i-2]

print(C[n]%10007)

타일을 넣는 방법은 2x1 타일을 넣는 방법, 1x2 타일을 넣는 방법으로 크게 두 가지로 나눌 수 있다. 2x1 타일부터 2xn 타일까지 차례대로 방법의 수를 C 리스트에 구해오다, n 타일에 도달했을 때 그 값을 print 해주면 된다.

base case로는 2x1 타일일 때는 2x1 타일만 넣을 수 있기 때문에 1가지가 되고, 2x2 타일일 때는 2x1 타일 두 개를 넣는 방법, 1x2 타일을 두 개 넣는 방법밖에 없기 때문에 2가지가 된다.