[DP] 9184번, 1904번

1. 신나는 함수 실행

링크 - 신나는 함수 실행

코드

def w(a,b,c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1

    if a > 20 or b > 20 or c > 20:
        return w(20,20,20)
    
    if mm[a][b][c]!=0:
        return mm[a][b][c]

    if a < b < c:
        mm[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
        return mm[a][b][c]
    else:
        mm[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
        return mm[a][b][c]

mm =[[[0 for col in range(21)] for row in range(21)] for depth in range(21)]
while True:
    a,b,c = map(int,input().split())
    
    if a==b==c==-1:
        break
    
    print('w({0}, {1}, {2}) = {3}'.format(a, b, c, w(a,b,c)))

문제 설명에 있는 식을 그대로 사용하면 되는 문제였다.

이 때 메모이제이션을 사용하기 위해서 만약 이전에 구한 값이 존재한다면 점화식을 사용하지 않고도 바로 출력할 수 있도록 했다.

2. 01타일

링크 - 01타일

코드

n = int(input())

dp = [0]*(n+1)

dp[1]=1
if n>1:
    dp[2]=2
if n>=3:
    for i in range(3,n+1):
        dp[i] = (dp[i-1]+dp[i-2])%15746
    

print(dp[n])

기본적인 dp문제
값을 업데이트할 때 나머지 연산을 해주면서 저장을 해줘야 한다.

안그러면 메모리초과 생김 ㄱ-