BOJ/백준-11727-python

문제

풀이

• 타일링 문제로 다이나믹 프로그래밍 단골 문제 중 하나이다.

n	경우의 수
1	1
2	3
3	5
4	11
5	21

• 위 테이블에서 확인할 수 있듯이 경우의 수가 n에 따라 일정한 규칙을 가지는걸 확인 할 수 있다.
• 점화식 = d[i] = d[i-2]*2 + d[i-1]
• bottom-up으로 구현하였다.

코드

# https://www.acmicpc.net/problem/11727
# boj, 11727: 2*n 타일링 2, python3
import sys

input = sys.stdin.readline

def dp(n):
    # 앞서 계산된 결과를 저장하기 위한 dp 테이블 초기화
    d = [0] * 1001

    d[1] = 1
    d[2] = 3

    # dp bottom-up
    for i in range(3, n+1):
        d[i] = (d[i-1] + d[i-2] * 2) % 10007

    return d[n]

if __name__ == '__main__':
    n = int(input())

    print(dp(n))

결과

출처 & 깃허브

BOJ 11727
github