😵 백준 9184번 신나는 함수 실행 풀이 ( Dynamic Programming, Memoization)

---

이 게시물은 개인적으로 알고리즘 공부한 내용과 이곳 저곳 검색하여 얻은 정보,

잡지식을 꾸준히 쌓아가는 글입니다.

출처는 최하단에 남겨두겠습니다. 자료나 궁금한점은 댓글로 질문해주세요.^^ 

---

Dynamic Programming - Memoization
동적계획법 - 메모이제이션

 

9184번 문제에 동적계획법을 활용하여 문제를 푸는데, 메모이제이션 개념을 활용하여 구현한다. 

Dynamic Programming / Memoization 메모이제이션은 재귀함수를 진행할때, 

값을 저장하여 반복되는 계산을 진행하지 않는 방법이다. 
재귀의 단점을 보완하는 중요한 개념이다. 동저계획법의 핵심이 되는 기술이다.

 

문제

재귀 호출만 생각하면 신이 난다! 아닌가요?
다음과 같은 재귀함수 w(a, b, c)가 있다.

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns: 1
if a > 20 or b > 20 or c > 20, then w(a, b, c) returns: w(20, 20, 20)
if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15) a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오.

입력

입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다.
입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다

출력

입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다.

풀이

MAX = 21    # 0 ~ 20 이 범위이기 때문에 21로 범위를 잡아준다.

# 입력값이 abc 세개 이기 때문에 범위를 3차 배열로 형성
dp = [[[0] * MAX for _ in range(MAX)] for __ in range(MAX)] 
# dp테이블에는 각 계산값이 담기는 형태로 들어간다.


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]:
        print(f'dp[{a}][{b}][{c}] = {dp[a][b][c]}')
        return dp[a][b][c]

    if a < b < c:
        print(f'a<b<c 의 경우이다. dp[{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]

    print(f'그밖의 경우 의 경우이다. 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, input().split())

    # 재귀함수를 멈추는 조건
    if (a, b, c) == (-1, -1, -1):
        break

    # 출력방식은 변경 가능하다.
    print("w(%d, %d, %d) = %d" % (a, b, c, w(a, b, c)))