[백준] 9184 - 신나는 함수 실행 (Python, Java)

[문제]

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

[풀이]

대표적인 다이나믹 프로그래밍(dp) 문제.
문제에 쓰여있는 대로 재귀함수 w(a,b,c)를 탑다운으로 구현하면 된다.
다만, 정말 그대로 하면 시간초과가 나기 때문에 메모이제이션으로 풀어야 한다.
그대로 구현하고 20, 20, 20 입력하면 함수가 10341번정도 호출된다.
메모이제이션으로 하지 않으면 20, 20, 20이 여러 번 입력되면 그만큼 계속 호출된다.

a, b, c 중 적어도 하나가 0보다 같거나 작거나 20보다 크면 상수값을 반환하기 때문에
1부터 20까지만 기억할 수 있게 하면 된다.
index에 -1하기 귀찮아서 그냥 21*21*21 의 배열을 만들었다.

내가 푼 풀이는 dp[a][b][c] == 0 일 때 값을 넣어주는 방식이다.
w(a,b,c) 가 0이 되는 (a,b,c) 쌍이 많다면 시간이 오래 걸릴 거라 생각했다.
a,b,c에 1~20을 각각 넣고 최종적인 dp의 값들을 확인해 봤다.
다행히? w(a,b,c) 가 0이 되는 (a,b,c) 쌍은 존재하지 않았다.

[코드]

[Python3]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

def w(a,b,c):     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)     if dp[a][b][c] == 0:         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)         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]   import sys; r=sys.stdin.readline dp = [[[0]*21 for _ in range(21)] for _ in range(21)] while True:     a,b,c = map(int, r().split())     if a == -1 and b == -1 and c == -1:         break     print('w(%d, %d, %d) = %d' %(a,b,c,w(a,b,c)))

[Java]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

import java.io.*; import java.util.Arrays;   public class Main{     static int[][][] dp;     public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         dp = new int[21][21][21];         while(true){             int[] num = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();                  if(num[0] == -1 && num[1] == -1 && num[2] == -1) break;             System.out.printf("w(%d, %d, %d) = %d\n",                  num[0],num[1],num[2],w(num[0],num[1],num[2]));         }     }     static int w(int a, int b, int c){         if(a <= 0 || b <= 0 || c <= 0) return 1;         if(a > 20 || b > 20 || c > 20) return w(20, 20, 20);         if(dp[a][b][c] == 0){             if(a < b && 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];     } }