[알고리즘][Python] 백준 11727 2xN 타일링 2 문제 풀이

📊알고리즘, 문제풀이/📈문제풀이 (PS)

Written by Donghak Park

문제 출처 : www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

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

www.acmicpc.net

문제 해석 : 1X2, 2X1, 2X2 타일을 사용해서 2XN의 타일을 모두 채우는 방법의 경우의 수를 구하는 문제이다.

문제 풀이 : 전형적인 DP 문제로 dp[i] = (dp[i-2]*2) + dp[i-1] 의 점화식을 사용해서 풀 수 있다.

풀이 코드

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

for i in range(4,N+1):
    dp.append((dp[i-2]*2) + dp[i-1] )

print(dp[N]%10007)

author : donghak park
contact : donghark03@naver.com

[알고리즘][Python] 백준 17626 Four Squares 문제 풀이 (0)	2021.01.15
[알고리즘][Python] 백준 17219 비밀번호 찾기 문제 풀이 (3)	2021.01.15
[알고리즘][Python] 백준 11726 2xN 타일링 문제 풀이 (0)	2021.01.15
[알고리즘][Python] 백준 11724 연결 요소의 개수 문제 풀이 (0)	2021.01.15
[알고리즘][Python] 백준 11723 집합 문제 풀이 (0)	2021.01.15

동학 개발 운동