[백준] 11726 : 2 x n 타일링 (Python)

 

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

 

---

 

아이디어

해당 문제는 DP의 대표적인 유형이다. 그렇다면, 연산 과정(경우의 수)을 통해, 왜 DP로 접근해야 하는지 살펴보자. n이 증가할 때 마다, 어떤 규칙이 있는지를 파악하는 것이 핵심 인사이트이다.

n이 1부터 3까지 일때, 각 n의 경우의 수를 구하는 과정. 이를 통한 점화식 발견.

먼저, n이 1과 2일때는 손쉽게 경우의 수가 고정되는 것을 알 수 있다. n이 3일때 또한 쉽게 발견할 수 있으나, 다음과 같은 생각을 해봐야 한다.

• n이 2일 때와 1일 때에서 타일링을 진행하면, n=3일 때의 타일을 만들 수 있지 않을까?

이를 통해, n이 1,2일 때의 각 경우를 통해 n=3 경우의 수를 구하게 되면, 점화식 가설을 세울 수 있게 된다. 해당 점화식이 과연 올바른지 확인하기 위해, 우리는 n=4일 때, 가설식을 이용하여 판단해보자.

직접 경우의 수를 구한 것과 가설식으로 구한 것을 비교

위의 사진을 통해, 해당 가설식을 바탕으로 구한 것과 동일하다는 것을 알 수 있으므로, 해당 점화식은 True라고 해석 가능하다. 사실, 해당 점화식을 자세히 생각해보면 '피보나치 수열 공식'과 같다는 것을 알 수 있다.

즉, '중복되는 연산을 줄이는 방법'이 피보나치에서의 중요 인사이트이고, 이를 통해 메모제이션 기법을 활용한다. 그러므로, 해당 문제는 DP로써 접근할 수 있다.

 

정답 코드

# https://www.acmicpc.net/problem/11726
# 2n 타일링
# dp

input=__import__('sys').stdin.readline

n=int(input())
dp=[0]*(1001)

dp[1]=1
dp[2]=2

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

print(dp[n])