백준 11726번 2×n 타일링 파이썬 풀이

Python

[Python] 백준 알고리즘 온라인 저지 11726 2×n 타일링

11726 2×n 타일링

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

11726번: 2×n 타일링

DP(동적 계획법)과 점화식을 이용하여 풀어야 하는 문제로 먼저 작은 수들의 경우의 수를 구해 이를 활용하여 코드를 작성하였다.

---

코드

import sys
input = sys.stdin.readline

n = int(input())
dp = [0, 1, 2, 3]

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

print(dp[n])

---

풀이

동적계획법에 관하여 따로 정리한 내용

 

작은 수부터 방법의 수를 정리해보면 [0, 1, 2, 3]이라는 dp가 만들어진다. 점화식은 dp[n] = dp[n-1]+dp[n-2]의 식이 만들어진다. 간단하게 설명하자면 

• n = 2 ( || , = )
• n = 3 ( ||| , |= , =|)
• n = 4 ( |||| , ||=, =|| , |=|  , ==) 

위와 같이 n = 4일때는 2x3 사각형을 채우는 경우에서 각각 1x2 도형을 채우는 경우, 2x2 사각형을 채우는 경우에서 각각 2x2 도형을 채우는 경우의 합을 이용할 수 있습니다. dp를 사용하는 이유는 이러한 값들을 저장하여 n값이 크더라도 빠르게 구할 수 있도록 하기 위함입니다.

dp 리스트에 추가함으로써 n값을 목표로 리스트를 만들어 나갈 수 있도록 코드를 작성하고 조건대로 10007을 나누어주면 n값을 구할 수 있게 됩니다.

---

풀이 결과

11726 풀이결과