[9148번] 신나는 함수 실행 JAVA☕

 

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

9184번: 신나는 함수 실행

알고리즘 [접근 방법]

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(a < b && b < c) {
		return w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
	}
	
	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);
}

이렇게 w함수가 주어졌기 때문에 구현은 따로할 필요가 없다.
이 부분을 동적계획법으로 풀어나가기 위해서는 처음 방문하는 재귀라면 계산을 통해 얻은 값을 메모리에 저장하고, 그 후 재방문을 할 경우 다시 계산하는 것이 아닌 저장된 값을 사용하라는 것이다.
이 문제에서는 a,b,c라는 변수가 작용하는 만큼 3차원 배열을 이용하여 풀이하면 된다.

static int dp[][][];	// 이미 배열이 생성되었다고 가정
 
static int w(int a, int b, int c) { 
 
	// 이미 계산되어 저장되어있는 경우 해당 값을 바로 반환 
	if(dp[a][b][c] != 0) {
		return dp[a][b][c];
	}
		
	if(a <= 0 || b <= 0 || c <= 0) {
		return 1;
	}
 
	/*
	 * a, b, c중 하나라도 20이 넘어가면 w(20, 20, 20)을 호출하기 때문에
	 * dp[20][20][20] 에 저장하고 반환하면 된다.
	 */
	if(a > 20 || b > 20 || c > 20) {
		return dp[20][20][20] = w(20, 20, 20);
	}
		
	if(a < b && b < c) {
		return dp[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
	}
	
	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);
}

대략적으로 이렇게 dp배열에 저장해두는 것과 이미 저장된 경우만 추가해주면 대부분 완성이 된다.

---

풀이 및 코드

 

import java.util.Scanner;
 
public class Main {
 
	/*
	 * 함수 w에서 a, b, c 중 20이 넘어가게 되면 w(20, 20, 20)을 호출하고,
	 * 0 이하일 경우는 1을 반환하기 때문에
	 * 각 배열의 크기가 21 (0~20)을 넘기지 않는다.
	 */
	static int[][][] dp = new int[21][21][21];
	
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);		
		
		while(true) {
			
			int a = in.nextInt();
			int b = in.nextInt();
			int c = in.nextInt();
			
			// -1 -1 -1 이 나오면 종료
			if (a == -1 && b == -1 && c == -1) {
				break;
			}
			
			System.out.printf("w(%d, %d, %d) = %d\n", a, b, c, w(a, b, c));
		}
		
	}
	
	static int w(int a, int b, int c) { 
		
		// a, b, c가 범위를 벗어나지 않으면서 메모이제이션이 되어있는 경우
		if(inRange(a, b, c) && dp[a][b][c] != 0) {
			return dp[a][b][c];
		}
		
		if(a <= 0 || b <= 0 || c <= 0) {
			return 1;
		}
		
		if(a > 20 || b > 20 || c > 20) {
			return dp[20][20][20] = w(20, 20, 20);
		}
		
		if(a < b && b < c) {
			return 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] = 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 중 하나라도 범위 밖의 수가
	 *  나올 수 있기 때문에 이를 체크를 해주기 위한 함수다.
	 */
	static boolean inRange(int a, int b, int c) {
		return 0 <= a && a <= 20 && 0 <= b && b <= 20 && 0 <= c && c <= 20; 
	}
}

문제 조건을 잘 읽어보면 세 변수 중 하나라도 0이하일 경우는 1, 20을 초관 경우에는 w(20,20,20)을 호출한다. 결과적으로 실제 쓰이는 범위는 0~20까지 밖에 안된다. 한마디로 dp[a][b][c]에 대하여 각 차원에 대해 21개(0~20)의 공간만 생성해준 뒤 메모이제이션을 해주면된다.
대신에 한가지 조건이 붙는다면, 처음 w을 호출할 때에는 음수 또는 20이 넘는 수가 입력될 수도 있기 때문에 배열을 참조하고자 할 때 IndexOutOfBoundException과 같은 잘못된 참조가 이루어질 수 있기에 이를 체크하기 위한 메소드 inRange()가 추가되었다.