TIL 39 | DP 신나는 함수실행 (백준 9184 python)

문제 바로가기

접근방식

DP기법 중 하나인 메모이제이션을 통해 재귀함수의 단점인 중복 연산을 방지하고 효율을 높여야한다.

메모이제이션을 하는 방식에는 리스트를 이용하는 방법과 딕셔너리를 이용하는 방법이 있다.

두 가지 방식을 모두 구현하였다. 결과 값에 유의미한 차이는 없었다.

딕셔너리를 이용한 메모이제이션 기법

import sys

memo = dict()

def w(a, b, c):
    
    #이미 계산된 결과가 존재하는 지 판단
    if (a,b,c) in memo.keys():
        return memo[(a,b,c)]

    # 계산된 결과가 존재하지 않는다면 
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    
    elif a > 20 or b > 20 or c > 20:
        memo[(20,20,20)] = w(20,20,20)
        return memo[(20,20,20)]

    elif a < b < c:
        memo[(a,b,c)] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
        return memo[(a,b,c)]
    else:
        memo[(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 memo[(a,b,c)]
    
while True:
    a,b,c = map(int,sys.stdin.readline().split())
    
    # 재귀함수 탈출 조건
    if (a,b,c) == (-1,-1,-1):
        break

		print("w({}, {}, {}) = {}".format(a,b,c,w(a,b,c)))

리스트를 이용한 메모이제이션 기법

import sys

memo = [[[0 for _ in range(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
    # 큰 숫자가 입력되어도 20으로 조정하기 위해 먼저 판단한다.
    elif a > 20 or b > 20 or c > 20:
        return w(20,20,20)


    #이미 계산된 결과가 존재하는 지 판단
    if memo[a][b][c]:
        return memo[a][b][c]

    #저장된 결과가 없다면 재귀함수로 계산한 결과를 저장
    if a < b < c:
        memo[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
    else:
        memo[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 memo[a][b][c]
    
while True:
    a,b,c = map(int,sys.stdin.readline().split())
    
    # 재귀함수 탈출 조건
    if (a,b,c) == (-1,-1,-1):
        break
    print("w({}, {}, {}) = {}".format(a,b,c,w(a,b,c)))

비하인드스토리

틀렸습니다! 딕셔너리로 구현한 코드의 채점 결과가 계속해서 틀리다고 나왔기 때문에 수정을 거듭하다 배열 방식을 시도했다. 두 가지 방식으로 완성하고 나니 출력 시 공백때문에 채점 결과가 오답이었음을 알게되었다. 허탈했지만 덕분에 한 문제에 대한 메모이제이션을 두 가지 방식으로 구현해봄으로써 서로를 비교하며 연습해볼 수 있는 시간이었다. 😂

오답원인 : 출력 값에.. 공백이 부족했기 때문..

print(f'w({a},{b},{c}) = {w(a,b,c)}') 
# 출력 시 w(a,b,c) = 답

print("w({}, {}, {}) = {}".format(a,b,c,w(a,b,c))) 
# 출력 시 w(a ,b, c) = 답