[파이썬] 단계별 백준 문제 풀기 - 9184 동적 계획법 1 (신나는 함수 실행)

문제링크

9184번: 신나는 함수 실행

문제

재귀 호출만 생각하면 신이 난다! 아닌가요?

다음과 같은 재귀함수 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)를 출력한다.

---

<<소스코드>>

import sys

#3차원 배열을 통해 메모이제이션! memo값에 추가해준다. n의 최대는 50이므로 51까지로 설정
memo = [[[0 for _ in range(51)] for _ in range(51)] for _ in range(51)]

for i in range(51) :
    for j in range(51) :
        for k in range(51) :
            if i == 0 or j == 0 or k == 0 : #0이 하나라도 있으면 1 반환
                memo[i][j][k] = 1

#문제에서 제시한 조건으로 함수 구현
def w(a, b, c) :

    if a <= 0 or b <= 0 or c <= 0 :
        return 1        

    if memo[a][b][c] != 0 :
        return memo[a][b][c]

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

    if 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]


    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 == -1 and b == -1 and c == -1 :
        break

    ans = 'w(%d, %d, %d) = %d' % (a,b,c,w(a,b,c))
    print(ans)

<<3차원 배열 안씀 - 정답코드 >>

 

import sys
memo = {

}

def w(a,b,c,memo):

    if (a,b,c) in memo:
        return memo[(a,b,c)]

    if a <= 0 or b <= 0 or c <= 0 :
        memo[(a,b,c)] = 1
        return 1

    elif a > 20 or b > 20 or c > 20 :
        memo[(a,b,c)] = w(20,20,20,memo)
        return w(20,20,20,memo)
   
    elif a < 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)
        return 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 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)

while True:
    a,b,c = map(int,sys.stdin.readline().split())
    if a == -1 and b == -1 and c == -1 :
        break

    print('w(%d, %d, %d) = %d' %(a,b,c, w(a,b,c,memo)))

 

<<결과값>>

1 1 1
w(1, 1, 1) = 2
2 2 2
w(2, 2, 2) = 4
10 4 6
w(10, 4, 6) = 523
50 50 50
w(50, 50, 50) = 1048576
-1 7 18
w(-1, 7, 18) = 1
-1 -1 -1

---

아 몰라.. 몰라서 답보고 풀었다ㅠㅠ 동적계획법의 개념은 알겠는데 3차원 배열은 또 뭐냐구요! 하

나는 왜 못 풀었을까요? 

 1) 문제 이해를 못함... 이게 왜 재귀야? 예제보고 이해했다. 

 2) 3차원 배열을 리스트로 만드는 것을 모름 

 3) %방식의 출력을 몰랐음

 

피보나치의 문제와 똑같았다. 메모이제이션을 이용해 동적 계획법으로 접근해야 풀 수 있는 문제였다. 

 

1) 문제이해하기!! a,b,c 셋 중 하나가 0보다 작으면 1이다. 

   즉 w(1,1,1)의 경우 맨 마지막 문장의 조건에 따르면

    w(0,1,1) + w(0,0,1) +w(0,1,0) -w(0,0,0) 인데, 0이 하나라도 있으면 1의 값이므로

    1 + 1 + 1 - 1 = 2값이 계산된다.

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)

2) 3차원 배열 리스트로 만들기!! 

높이2 , 세로4, 가로3인 3차원 리스트를 만들기 위해

아래와 같은 배열을 만들어 주었다. 

[[[ 0 for _ in range(3) ] for _ in range(4) ] for in range(2) ]

그리하여, 

[[[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]], [[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]]

[[[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]], [[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]]

 

이분의 블로그를 참조하였다. 감사합니다!!

 

3) %방식의 출력

아주 유용한 방식이다. 자주 써먹을 것 같다

print("정수출력: %d" % (d에넣고싶은것) )