동적 계획법(Dynamic programming), 백준 9184번

동적 계획법(Dynamic programming)

• 큰 문제를 작은 하위 문제로 나누어 해결하는 최적화 기법
• 중복 계산을 피하기 위해 계산 결과를 저장하여 속도를 향상 시키는 방식

다음과 같은 상황에서 유용하게 사용됨

1. 최적 부분 구조(Optimal Substructure)

• 큰 문제를 작은 하위 문제로 나눠, 작은 문제의 해결 방법을 결합하여 큰 문제에 대한 최적의 해를 구하는 것

2. 중복 부분 문제(Overlapping Subproblems)

• 동일한 하위 문제를 풀때의 중복 계산을 방지하기 위해, 이를 한번만 계산하고 결과를 저장하여 해를 구하는 것

동적 계획법

1. 하위 문제 정의 : 큰 문제를 작은 하위문제로 나누되, 본 문제보다 크기가 작으며 쉽게 풀수 있어야 함.
2. 하위 문제 해결 : 가장 작은 하위 문제 부터 시작하여 해결해 나가되, 중복 계산을 피하기 위해 결과를 저장해야 함. 이 저장소를 "메모이제이션(Memoization)" 라고 함.
3. 상위 문제 해결 : 하위 문제들을 결합하여 더 큰 상위 문제들을 해결해 나가되, 이미 계산한 결과들을 재활용 함.

동적 계획법 방식

1. Top-Down 방식

• 재귀 호출과 메모이제이션으로 문제 해결

2. Bottom-Up 방식

• 작은 하위 문제 부터 시작 하여 상위 문제까지 순서대로 해결

예시 문제 - 백준 9184번

1. 문제

문제 : https://www.acmicpc.net/problem/9184

2. 코드

import sys
dp = [[[0]*21 for _ in range(21)] for _ in range(21)]

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 dp[a][b][c]:
        return dp[a][b][c]

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

    dp[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 dp[a][b][c]

while True:
    a, b, c = map(int, sys.stdin.readline().rstrip().split())
    if a == -1 and b == -1 and c == -1:
        break
    ans = w(a, b, c)
    print("w(%d, %d, %d) = %d" %(a, b, c, ans))