📌 문제

[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)를 출력한다.

✔️ 제한

-50 ≤ a, b, c ≤ 50

💡 코드

✅ main 메서드에서 무한루프를 돌려서 입력 받은 a, b, c가 모두 -1인 경우에 반복문을 빠져나가게 한다. 세 값이 모두 -1이 아니라면 w(a, b, c) 메서드를 호출하여 출력 형식에 맞게 출력한다.

w(a, b, c) 메서드의 경우 문제에서 주어진 조건을 그대로 활용하되, 재귀 함수의 호출 시 중복 연산을 수행할 수 있으므로 메모이제이션을 통해 한 번 수행된 값을 따로 저장해준다.

a, b, c의 값에 따라 결과가 달라지므로 3차원 배열 arr[][][]를 선언한다. 이 때, 문제의 조건에 따라 배열의 크기를 21으로 설정한다. (a=1, b=1, c=1 ➡️ arr[1][1][1]) 문제의 조건은 다음과 같다.

1. a, b, c 중 하나라도 음수라면 return 1
2. a, b, c 중 하나라도 20보다 크면 return w(20, 20, 20)
3. a < b < c 라면 return w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
4. 그 외에는 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)

1번의 경우, 1을 바로 리턴하므로 값을 따로 기억할 필요가 없고, 2, 3, 4번의 경우 이후에 같은 경우가 발생할 수 있는데, 그 때마다 재귀함수를 호출하는 것은 비효율적이므로 처음 연산을 수행할 때 arr[a][b][c]에 결과값을 저장한다.

이렇게 값을 저장한 후에 다음 수행에서 같은 경우가 주어진다면 arr[a][b][c]의 값이 0이 아닌 다른 결과값이므로 따로 재귀를 수행하지 않고 저장된 값을 바로 꺼낼 수 있다. 이 때 arr[a][b][c] != 0을 if(a > 20 || b > 20 || c > 20)보다 먼저 수행하면 인덱스 범위 참조 예외가 발생하므로 주의해야 한다!

import java.io.*;
import java.util.*;
public class Main {
	
	static int[][][] arr = new int[21][21][21];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		while(true) {
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			if(a == -1 && b == -1 && c == -1) break; // 마지막
			
			sb.append("w(" + a + ", " + b + ", " + c + ") = ").append(w(a, b, c)).append("\n");
		}
		bw.write(sb + "");
		
		br.close();
		bw.close();
	}
	
	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(arr[a][b][c] != 0) return arr[a][b][c];
		
		if(a < b && b < c) return arr[a][b][c] =
		    w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
		
		return arr[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);
	}
}