[백준/Python] 9184 신나는 함수 실행

[백준/Python] 9184 신나는 함수 실행

정답 코드 및 설명

전체 코드

def w(a, b, c, memo):
    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, memo)
    if memo[a][b][c] != -1:
        return memo[a][b][c]
    if a < b and b < c:
        memo[a][b][c] = w(a, b, c-1, memo) + w(a, b-1, c-1, memo) - w(a, b-1, c, memo)
    else:
        memo[a][b][c] = w(a-1, b, c, memo) + w(a-1, b-1, c, memo) + w(a-1, b, c-1, memo) - w(a-1, b-1, c-1, memo)
    return memo[a][b][c]

# 메모이제이션을 위한 3차원 배열 초기화 (인덱스 조정 필요 없이 직접 사용 가능)
memo = [[[-1 for _ in range(51)] for _ in range(51)] for _ in range(51)]

while True:
    a, b, c = map(int, input().split())  # 사용자로부터 a, b, c 입력받기
    if a == -1 and b == -1 and c == -1:  # 모두 -1인 경우 반복문 종료
        break
    result = w(a, b, c, memo)  # w 함수를 호출하여 결과 계산
    print(f"w({a}, {b}, {c}) = {result}")  # 결과 출력

먼저 문제에서 제공하는 w함수를 파이썬으로 작성한다. w함수를 잘 보면 w함수 내에서 재귀 호출을 하고 있다. 때문에 a,b,c 에 각각 어떤 숫자가 왔을 때 이미 계산한 적이 있는 값이 있을 것이다.

때문에 입력값에 대한 함수의 결과를 메모이제이션하는 방식으로 구현할 수 있다. 중복계산을 방지 하는 것이다.

재귀함수 w(a,b,c) 는 다음과 같다
1 베이스 케이스 처리

• a <= 0 or b <= 0 or c <= 0인 경우, 1을 반환
• a > 20 or b > 20 or c > 20인 경우, w(20, 20, 20)을 반환

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, memo)

2. 메모이제이션을 체크하여, 이미 계산된 값이 있는 경우 그 값을 반환

if memo[a][b][c] != -1:
        return memo[a][b][c]
        
        ...
        
  return memo[a][b][c]

3. 주어진 조건에 따라 w(a, b, c)를 재귀적으로 계산하고, 그 결과를 메모이제이션 배열에 저장한 후 반환

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