[백준] 9184번 : 신나는 함수 실행

문제

 

 

접근 방식

문제에 적힌거처럼 위 함수를 그대로 구현하고 15, 15, 15 이상의 값들을 넘겨주면

재귀의 깊이가 너무 깊어져 시간 초과가 발생한다.

 

중복된 호출을 계속해서 반복하기 때문인데

이러한 문제를 해결하기 위해서는 간단하게 중복된 호출을 하지 않으면 되고

이를 해결하는 방법은 DP와 메모이제이션이 있고

이번에는 메모이제이션을 사용해서 풀어보겠다.

 

우선 입력의 범위가 -50부터 50까지이기 때문에

배열을 101칸 만들고 50씩 더해서 인덱스를 계산해줄까 생각했는데

문제의 코드를 보고 나니 어차피 1이상 20이하까지만 계산하기 때문에

그 외의 값들을 처리해줄 필요가 없다.

 

그래서 계산 결과를 처리해줄 3차원 배열을 각 21칸씩 만들어

a, b, c의 경우의 수마다 값을 저장해주면 된다.

 

이후 함수를 호출할 때마다 이미 저장된 값이 있으면

저장된 값을 리턴하고 그렇지 않은 경우에만

함수를 호출해 값을 배열에 저장해주면

중복된 계산을 피할 수 있다.

 

DP로 푸는 방법도 간단하게 설명만 하자면

똑같이 3차원 배열을 만든 후에

a, b, c가 각각 0이하인 경우를 모두 1로 채워주고

나머지도 문제의 코드의 조건식대로 값을 채워주면 된다.

 

풀이

public class Main {

	private static int[][][] dp = new int[21][21][21];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		while (true) {
			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(").append(a).append(", ").append(b).append(", ").append(c).append(") = ");

			sb.append(w(a, b, c)).append("\n");
		}

		System.out.println(sb);
	}

	private 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) {
			if (dp[20][20][20] == 0) dp[20][20][20] = w(20, 20, 20);
			return dp[20][20][20];
		}

		if (a < b && b < c) {
			dp[a][b][c-1] = dp[a][b][c-1] != 0 ? dp[a][b][c-1] : w(a, b, c - 1);
			dp[a][b-1][c-1] = dp[a][b-1][c-1] != 0 ? dp[a][b-1][c-1] : w(a, b - 1, c - 1);
			dp[a][b-1][c] = dp[a][b-1][c] != 0 ? dp[a][b-1][c] : w(a, b - 1, c);
			return dp[a][b][c-1] + dp[a][b-1][c-1] - dp[a][b-1][c];
		}

		dp[a-1][b][c] = dp[a-1][b][c] != 0 ? dp[a-1][b][c] : w(a - 1, b, c);
		dp[a-1][b-1][c] = dp[a-1][b-1][c] != 0 ? dp[a-1][b-1][c] : w(a - 1, b - 1, c);
		dp[a-1][b][c-1] = dp[a-1][b][c-1] != 0 ? dp[a-1][b][c-1] : w(a - 1, b, c - 1);
		dp[a-1][b-1][c-1] = dp[a-1][b-1][c-1] != 0 ? dp[a-1][b-1][c-1] : w(a - 1, b - 1, c - 1);

		return dp[a-1][b][c] + dp[a-1][b-1][c] + dp[a-1][b][c-1] - dp[a-1][b-1][c-1];
	}
}