[백준/DP] 11726 2×n 타일링 (Python, 파이썬)

 

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

11726번: 2×n 타일링

 

2*n 직사각형을 1*2, 2*1 타일로 채우는 방법의 수

D[n] = 2 X n 직사각형을 채우는 방법의 수

 

2*n 직사각형이 있을 때, 가장 오른 쪽에 타일을 놓을 수 있는 방법은 총 2가지가 있다.

1) 세로 블록이 하나 오는 경우 : D[n-1]

2) 가로 블록 두개 오는 경우 : D[n-2]

D[n] = D[n-1] + D[n-2]

 

2*5의 경우 수는 (1) 2*3경우에서 블록 두 개를 더 붙이는 것과 (2) 2*4 경우에서 블록 한 개를 더 붙이는 것의 경우의 수를 더한 값이다.

 

위의 점화식을 이용하여 짠 코드는 다음과 같다. 결론부터 말하자면 런타임에러가 생겼다ㅠㅠ

n = int(input())
D = [0 for _ in range(n+1)]

D[1] = 1
D[2] = 2

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

print(D[n]%10007)

 

 

왜냐, 위에는 1 과 2에 대한 예외 처리가 없기 때문이다. if문으로 간단하게 처리해줬다.

다음은 정답코드이다.

n = int(input())
D = [0 for _ in range(n+1)]

if n < 3: print(n)
else:
    D[1] = 1
    D[2] = 2

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

    print(D[n]%10007)