[Python/파이썬] 백준 알고리즘 11726번 - 2×n 타일링 (DP)

 

 

 

 

<풀이>

n = int(input())

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

print(dp[n] % 10007)

처음에는 너무 복잡하게 생각했다.

그냥 간단하게 수열의 점화식을 찾고, 그 값들을 리스트에 저장하는 메모이제이션 방법을 사용해 풀면 되는 것이었다.

 

나열되는 방법의 수들의 규칙성을 찾고 그것을 점화식으로 표현하면 다음과 같다.

dp[i] = dp[i-2] + dp[i-1]

 

이 점화식을 이용해 리스트에 값들을 메모이제이션하기에 앞서 2x1 크기의 직사각형을 채우는 방법의 수는 1, 2x2 크기의 직사각형을 채우는 방법의 수는 2이므로 dp[1], dp[2]에 각각 1과 2를 먼저 넣는다.

 

그리고 for문을 3부터 1000까지 돌리며 리스트에 값들을 넣는다.

 

 

 

<핵심 정리>

1. 동적 계획법은 큰 문제를 작은 문제로 쪼갠 다음 점화식을 구해 재귀적인 구조를 활용하여 큰 문제를 해결하는 방식이다.

2. 메모이제이션하는 리스트의 초기값을 먼저 설정해놓고 시작할수도 있다.