백준 9184 - 신나는 함수실행 (동적계획법)

문제를 풀기에 앞서 새로운 알고리즘 유형인 동적계획법 알고리즘에 대해 공부해보도록 하자.

https://hongjw1938.tistory.com/m/47

알고리즘 - Dynamic Programming(동적 계획법)

이 포스팅에 자세하게 나와져 있다.

 

결론적으로, 어떠한 문제가 재귀 알고리즘으로 풀릴 수 있다고 했을 때,  그 문제는 동적계획법 알고리즘으로도 풀릴 수 있다. 근데 왜 굳이 재귀와 동적계획법을 구분하여 사용하며, 그 둘의 차이점은 무엇일까?

 

재귀 알고리즘은 말 그대로 재귀 함수를 사용하여 함수 안에서 자기 자신 함수를 계속해서 호출하는 것이다.

하지만, 동적계획법 알고리즘은 어떠한 결과 값을 내기 위하여 필요한 결과들을 계속해 저장해놔 계속 함수를 호출하지 않고도 반복문만으로도 문제를 해결할 수 있다.

간단한 문제는 재귀 알고리즘을 사용하여 코드를 간결하게 작성할수도 있지만, 계산이 복잡한 문제에서는 하나의 결과값을 내는데 있어서 불필요하게 함수를 많이 호출하여 많은 시간이 걸린다는 단점이 있다. 따라서 문제의 복잡도와 시간을 따져서 동적계획법 알고리즘을 선택적으로 사용할 줄 알아야 한다.

 

https://www.acmicpc.net/problem/9184 

9184번: 신나는 함수 실행

 

의사코드가 있기 때문에 처음부터 구현을 할 필요는 없지만, 재귀 알고리즘을 동적계획법 알고리즘으로 바꾸는게 생소해서 못풀었다.

다른 사람의 풀이를 보니 매우 간단했다.

 

 

 

import sys
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:
        return w(20,20,20)

    if dp[a][b][c]:
        return dp[a][b][c]

    if a<b<c:
        dp[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, 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 i in range(21)] for i in range(21)] for i in range(21)]
while True:
    a, b, c = map(int, sys.stdin.readline().split())
    if a == b == c == -1:
        break
    print(f"w({a}, {b}, {c}) = {w(a, b, c)}")

 

위의 코드를 풀이해보자.

1. a, b, c 셋 중 20이 넘는 것이 하나라도 있을 경우 => w(20,20,20)이다.

1번을 통해 a, b, c 가 20이 넘지 않을 때만 답을 구하면 된다는 것을 알 수 있다.

(어차피 20이 넘으면  w(20,20,20)값으로 통일이니까 ㅇㅇ)

 

2. 1번을 따라 답을 저장하기 위해 크기가 21인 3차원 배열을 선언하였다.

 

3. 의사코드대로 조건에 따라 정해진 답을 리턴하는 조건문을 작성한다.

 

4. 조건문에 포함되지 않아 계산이 필요한 경우 계산을 한 뒤, 배열에 저장해준다.

 

5. 배열에 저장한 뒤, 원하는 값이 있으면 빼와 바로 사용할 수 있도록 한다.

(재귀는 배열에 저장안하고 그냥 무작정 재귀를 돌려버리니까 복잡한 문제는 시간이 오래걸리는데 동적계획법을 사용하니 이러한 한계를 극복할 수 있다는 것을 직접적으로 느낄 수 있다.)

if dp[a][b][c]:
    return dp[a][b][c]

이 코드를 작성해줌으로써, 원하는 값이 있는지 먼저 확인 후, 없을 경우에만 계산을 하도록 하는 것이다.