NAIAHD

14852_타일 채우기 3

출처 : 백준

2×N 크기의 벽을 2×1, 1×2, 1×1 크기의 타일로 채우는 경우의 수를 구해보자.

풀이 참조 :

import sys
sys.setrecursionlimit(10**6)

d = [0] * 1000001
def dp(n):
    if n == 0 :
        return 1
    if n == 1:
        return 2
    if n == 2:
        return 7
    if (d[n]!=0):
        return d[n]
    result = 3 * dp(n-2) + 2* dp(n-1)
    for i in range(3,n+1):
        result += (2 * dp(n-i)) % 1000000007
    d[n] = result
    return d[n]

n = int(input())
print(dp(n))

답은 정확하게 나오는데 시간초과이다.

비정상적이고 비효율적이다.

=>2차원 다이나믹 프로그래밍

d = [[0]*2]* 1000001

def dp(n):
    d[0][0] = 0
    d[1][0] = 2
    d[2][0] = 7
    d[2][1] = 1
    print(d[0][0])
    for i in range(3,n+1):

        d[i][1] = (d[i-1][1]+d[i-3][0]) % 1000000007
        d[i][0] = (3 * d[i-2][0] + 2 * d[i-1][0] + 2 * d[i][1]) % 1000000007
    return d[n][0]
n = 3
dp(n)

d = [[0]*2]* 1000001이렇게 선언하면 이상하게 나온다.

0으로 초기화했는데 7로 나와서 다음 과 같은 방식으로 list를 초기화해야 한다.

d = [[0]*2 for _ in range(1000001)]

def dp(n):
    d[0][0] = 0
    d[1][0] = 2
    d[2][0] = 7
    d[2][1] = 1

    for i in range(3,n+1):

        d[i][1] = (d[i-1][1]+d[i-3][0]) % 1000000007
        d[i][0] = (3 * d[i-2][0] + 2 * d[i-1][0] + 2 * d[i][1]) % 1000000007
    return d[n][0]
n = 3
dp(n)