[백준 11726 파이썬] 2×n 타일링 (실버3, 다이나믹 프로그래밍)

알고리즘 유형 : 다이나믹 프로그래밍
풀이 없이 스스로 풀었나요? : ⭕

---

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

솔루션

n이 1이라면 세로로만 세울 수 있으므로 방법은 한가지이다.

n이 2라면 세로로 두개 혹은, 가로로 두개로 방법은 두가지이다.

n이 3이라면 두 가지 경우로 나눌 수 있다.
맨 끝부분이 세로 하나인 경우, 남은 2개를 배치하는 방법은 n=2인 경우의 수와 같다.
맨 끝부분이 가로 두 개인 경우, 남은 하나를 배치하는 방법은 n=1인 경우의 수와 같다.
이 두 가지 경우를 더하면 n이 3일 때 경우의 수를 구할 수 있다.

n=4일 때도, 똑같이 두 가지 경우로 나눠서 풀 수 있다.
맨 끝부분이 세로 하나인 경우, 남은 3개를 배치하는 방법은 n=3인 경우의 수와 같다.
맨 끝부분이 가로 두 개를 둘 경우, 남은 2개를 배치하는 방법은 n=2인 경우의 수와 같다.
이 두 가지 경우를 더하면 n=4일 때 경우의 수를 구할 수 있다.

소스 코드

import sys

input = sys.stdin.readline

if __name__ == "__main__":
    n = int(input())
    dy = [0] * (n + 1)
    if n < 3:
        print(n)
    else:
        dy[1] = 1
        dy[2] = 2
        for i in range(3, n + 1):
            dy[i] = dy[i - 2] + dy[i - 1]
        print(dy[n] % 10007)

---

후기

점화식을 구하는 데 큰 어려움이 없어서 쉽게 풀 수 있었다.