[BEAKJOON] 백준 11726번 : 2xn 타일링

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

11726번: 2×n 타일링

문제

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

 

문제 해결

패턴을 먼저 찾아보자.

# 1 - 1 -> |
# 2 - 2 -> =, ||
# 3 - 3 -> |=, =|, |||
# 4 - 5 -> ||=, |=|, ||||, ==, ||=
# 5 - 8 => |||||, |||=, =|||, |=||, ||=|, |==, ==|, =|=,

마치 피보나치 수열처럼, 앞의 n-1, n-2의 값을 더하면 n의 값이 된다.

예를 들어서, n = 3일때,

n-1의 경우에 수인 =, ||에 " | "를 맨 끝에 하나씩 붙여주면, =|, ||| 이 된다.

n-2의 경우에 수인 | 에 " = "를 맨 끝에 붙여주면 |= 이 되어서,

총 2x3일때 경우의 수인 |=, =|, ||| 가 되는 것이다.

 

큰 값들도 마찬가지로 작동한다.

 

근데 다시 생각해보면 이는 당연한 방법의 해결이다.

n-2 에 있는 경우의 수는 당연히 작대기 두개를 추가하면 n의 경우의 수가 될 것이고(2개 이전이었으니, 작대기 2개)

n-1에 있는 경우의 수는 이전에 있었던 것들의 최선의 방안이며, 거기에 작대기 하나를 추가해야 n의 경우의 수가 될 것이다.

 

 

 

해결코드

num = int(input())

dp = list()
dp.append(1)
dp.append(2)

for i in range(2, num):
    dp.append((dp[i-1]+dp[i-2])%10007)

print(dp[num-1])