세상을 더 좋게

[백준] 11727 '2×n 타일링 2' 파이썬(python) 본문

Algorithm/DP

[백준] 11727 '2×n 타일링 2' 파이썬(python)

나는SOU 2021. 11. 19. 00:00

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

 

11727번: 2×n 타일링 2

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.

www.acmicpc.net

n = int(input())

dp = [0] * 1001		# DP 테이블 만들기. 범위가 1000까지이므로 1001까지 받는다.

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

for i in range(3, 1001) :		# 점화식을 이용하여 바텀업 방식으로 DP 알고리즘 이용
	dp[i] = dp[i-1] + 2 * dp[i-2]
    
print(dp[n] % 10007)

Point

  • DP를 이용한 알고리즘
  • 이전 11726문제에서 점화식이 약간 수정된 문제

'Algorithm > DP' 카테고리의 다른 글

[백준] 10844 '쉬운 계단 수' 파이썬(python)  (0) 2021.12.04
[백준] 16194 '카드 구매하기 2' 파이썬(python)  (0) 2021.11.25
[백준] 11052 '카드 구매하기' 파이썬(python)  (0) 2021.11.19
[백준] 9095 '1, 2, 3 더하기' 파이썬(python)  (0) 2021.11.19
[백준] 11726 '2×n 타일링' 파이썬(python)  (0) 2021.11.19
'Algorithm/DP' Related Articles more