BOJ/백준-11726-python

문제

풀이

• 타일링 문제로 모든 경우의 수를 체크해야하는 문제이므로 대표적인 다이나믹 프로그래밍 문제이다.
• n에 값에 따른 경우의 수는 아래와 같다.

n	경우의 수
1	1
2	2
3	3
4	5
5	8
6	13
7	21
8	34
9	55

• 위 테이블에서 확인할 수 있듯이 n이 3인 시점부터 d[i] = d[n-1] + d[n-2] 점화식이 성립한다.
• bottom-up 방식을 활용하여 구현하였다.

코드

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

input = sys.stdin.readline

def dp(n):
    # dp table 초기화
    d = [0] * 1001

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

    return d[n]

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

    print(dp(n))

결과

출처 & 깃허브

BOJ 11726
github