[백준 9184번] 신나는 함수 실행 (java)

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

9184번: 신나는 함수 실행

 

다이나믹 프로그래밍으로 풀었다.

처음에 단순히 삼중 for문을 사용하여 풀었는데 결과가 '틀렸습니다' 가 떴다.

import java.io.*;

public class Main {

	static int[][][] dp = new int[51][51][51];

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		for (int i = 0; i <= 50; i++) {
			for (int j = 0; j <= 50; j++) {
				for (int k = 0; k <= 50; k++) {
					if (i == 0 || j == 0 || k == 0)
						dp[i][j][k] = 1;
					else if (i > 20 || j > 20 || k > 20)
						dp[i][j][k] = dp[20][20][20];
					else if (i < j && j < k)
						dp[i][j][k] = dp[i][j][k - 1] + dp[i][j - 1][k - 1] - dp[i][j - 1][k];
					else
						dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - 1][k] + dp[i - 1][j][k - 1]
								- dp[i - 1][j - 1][k - 1];

				}

			}
		}

		while (true) {
			String[] sarr = br.readLine().split(" ");
			int a = Integer.parseInt(sarr[0]);
			int b = Integer.parseInt(sarr[1]);
			int c = Integer.parseInt(sarr[2]);

			if (a == -1 && b == -1 && c == -1)
				break;

			bw.write("w(" + a + ", " + b + ", " + c + ") = " + dp[Math.max(a, 0)][Math.max(b, 0)][Math.max(c, 0)]
					+ "\n");
		}

		bw.flush();

	}

}

 

위 코드에서의 반례 : w(1, 1, 21) = 0

원래 옳은 답 : w(1, 1, 21) = 1048576

 

위의 문제 설명대로라면 w(1, 1, 21) = w(20, 20, 20) 이 맞다. 그러나 삼중반복문이 dp[1][1][21] 차례일 때는 아직

dp[20][20][20]  에 대해서 반복문이 돌지 않았기 때문에 dp[20][20][20] 에는 0 이 들어있는 상태이다.

i = 1, j = 1 일 때가 i =20, j = 20 일 때보다 먼저 실행되기 때문이다.

 

그래서 일단 i, j, k  모두 20일때까지만 반복문을 실행한 후에,

다시 0부터 50까지 삼중 반복문을 돌도록 수정하였다.

 

정답인 코드는 아래와 같다.

 

소스코드 :

 

	import java.io.*;
	public class n09184 {
	static int[][][] dp = new int[51][51][51];
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	for (int i = 0; i <= 20; i++) {
	for (int j = 0; j <= 20; j++) {
	for (int k = 0; k <= 20; k++) {
	if (i == 0 || j == 0 || k == 0)
	dp[i][j][k] = 1;
	else if (i < j && j < k)
	dp[i][j][k] = dp[i][j][k - 1] + dp[i][j - 1][k - 1] - dp[i][j - 1][k];
	else
	dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - 1][k] + dp[i - 1][j][k - 1]
	- dp[i - 1][j - 1][k - 1];
	}
	}
	}
	for (int i = 0; i <= 50; i++) {
	for (int j = 0; j <= 50; j++) {
	for (int k = 0; k <= 50; k++) {
	if (i == 0 || j == 0 || k == 0)
	dp[i][j][k] = 1;
	else if (i > 20 || j > 20 || k > 20)
	dp[i][j][k] = dp[20][20][20];
	else if (i < j && j < k)
	dp[i][j][k] = dp[i][j][k - 1] + dp[i][j - 1][k - 1] - dp[i][j - 1][k];
	else
	dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - 1][k] + dp[i - 1][j][k - 1]
	- dp[i - 1][j - 1][k - 1];
	}
	}
	}
	while (true) {
	String[] sarr = br.readLine().split(" ");
	int a = Integer.parseInt(sarr[0]);
	int b = Integer.parseInt(sarr[1]);
	int c = Integer.parseInt(sarr[2]);
	if (a == -1 && b == -1 && c == -1)
	break;
	bw.write("w(" + a + ", " + b + ", " + c + ") = " + dp[Math.max(a, 0)][Math.max(b, 0)][Math.max(c, 0)]
	+ "\n");
	}
	bw.flush();
	}
	}

view raw 9184.java hosted with ❤ by GitHub