[다이나믹 프로그래밍] 11726번 - 2xn 타일링

[백준] 11726번 - 2xn 타일링

(한줄평) 쉽게 해결할 수 있었던 문제!

유사 문제: https://hseungyeon.tistory.com/287

[다이나믹 프로그래밍] ▲ 문제3 - 바닥 공사(223p)

 

풀이 시간: 10분 이내

1) 문제 해결 아이디어

가로 길이: n, 세로 길이: 2 인 직사각형 바닥을 1*2, 2*1 2가지 타일로 채울 수 있는 경우의 수를 10007로 나눈 나머지를 구하는 문제다. 이 문제는 다이나믹 프로그래밍의 기초 예제에서 빠질 수 없는 타일링 문제 유형이다.

 

<마지막 타일이 채워지는 경우의 수>

1. 2*1 타일 1개가 마지막에 들어갈 경우, 앞에 있는 직사각형의 길이는 (i - 1)이 되므로 길이가 (i - 1)인 타일을 채우는 경우의 수와 같다.

2. 1*2 타일 2개가 마지막에 들어갈 경우, 앞에 있는 직사각형의 길이는 (i - 2)가 되므로 길이가 (i - 2)인 타일을 채우는 경우의 수와 같다.

 

<점화식> 

 

2) 소스코드

n = int(input())  # 가로 길이
d = [1] * n  # 길이가 i인 직사각형을 채우는 경우의 수
if n >= 2:
  d[1] = 2
  for i in range(2, n):
    # 길이가 (i-1), (i-2)인 직사각형을 채우는 경우의 수의 합
    d[i] = (d[i - 1] + d[i - 2]) % 10007
print(d[n - 1])