[백준] 9184번 : 신나는 함수 실행 (파이썬)

4월 7일에 풀었는데 오류인지 뭔지.. 업로드 되었는데 목록에 표시가 안되어 재업로드 한다.

문제

나의 답안

import sys
input=sys.stdin.readline

def w(a,b,c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    elif a > 20 or b > 20 or c > 20:#20보다 크면 통일
        return w(20, 20, 20)
    
    if dp[a][b][c]:#dp값이 존재하면 리턴
        return dp[a][b][c]
    
    if a < b and 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]

    else:
        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]

dp=[[[0 for _ in range(21)] for i in range(21)] for i in range(21)]
#0으로 초기화 된 3차원 배열 선언(20보다 크면 w(20,20,20)으로 통일,0~20)

while True:
    a,b,c=map(int,input().split())

    if a==-1 and b==-1 and c==-1:
        break
    print('w({}, {}, {}) = {}'.format(a,b,c,w(a,b,c)))

접근 방법

• dp문제이다. dp문제에선 배열을 필요한만큼 미리 초기화해주어야 한다.(값을 저장해놓아야 하기 때문)
• a,b,c가 20보다 크다면 w(20,20,20)으로 값이 일정해지므로 0부터 20까지 3차원 배열을 선언해준다.
• 나머지 부분은 문제에서 제시한 대로 구현하면 된다.
  문제에서 제시한 재귀함수는 파이썬으로 다음과 같이 표현 가능하다.

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

    if a > 20 or b > 20 or c > 20:
        return w(20, 20, 20):

    if a < b and b < c:
        return w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c):
    else:
        return 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,b,c에 해당 하는 dp값이 존재하면 dp를 따로 구할 필요없이 리턴해주면 되고, 없다면 새로 구해서 리턴해주면 된다.