몽상실현개발주의

[BOJ] 11727 / 2×n 타일링2 / Python 본문

Algorithm PS/BOJ

[BOJ] 11727 / 2×n 타일링2 / Python

migrationArc 2021. 5. 10. 10:45

[BOJ] 11727 / 2×n 타일링2 / Python

[BOJ] 11727 / 2×n 타일링2 / Python

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

 

11727번: 2×n 타일링 2

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

www.acmicpc.net

 

풀이

11726 / 2 X n 타일링 문제에 조건이 추가되었다.

N = 1 -> 1
N = 2 -> 3
N = 3 -> 5
N = 4 -> 11
N = 5 -> 21

추가된 조건의 경우의 수는 위와 같았다.

점화식: dp(N) = dp(N-1) + 2*dp(N-2)

 

Tabluation 을 이용한 풀이는 다음과 같다.

N = int(input())
dp = [0, 1, 3] + [0] * N

for i in range(3, N+1):
    dp[i] = dp[i-1] + (2*dp[i-2])
    
print(dp[N]%10007)
저작자표시

'Algorithm PS > BOJ' 카테고리의 다른 글

[BOJ] 10844 / 쉬운 단계 수 / Python  (0) 2021.05.10
[BOJ] 9095 / 1, 2, 3 더하기 / Python  (0) 2021.05.10
[BOJ] 11726 / 2×n 타일링 / Python  (0) 2021.05.09
[BOJ] 1463 / 1로 만들기 / Python  (0) 2021.05.07
[BOJ] 입출력 기본 문제 풀이  (0) 2021.05.06
'Algorithm PS/BOJ' Related Articles more
Comments