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

동적 계획법(DP)을 공부한 뒤, DP관련 문제인 9184번 : 신나는 함수 실행을 풀었다.

 

 

동적 계획법에 대해 아직 이해하지 못했다면 다음의 블로그에서 확인하면 된다.

https://lucy1215.tistory.com/23

[알고리즘] 동적 계획법 (Dynamic Programming)

 

---

<문제>

 

<문제 해석>

동적계획법(DP)을 이용하여 a,b,c가 주어질 때, 재귀함수 w(a,b,c)를 출력해라.

 

 

 

<문제 해결>

문제에 코드 식이 많아 복잡해 보이지만 어렵지 않은 문제였다.

그냥 문제의 코드 식을 그대로 사용하면 되는 문제이기 때문이었다.

 

 

동적 계획법(DP)를 사용하기 위해 값을 저장해놓을 dp[][][]배열이 필요하다.

 

 

dp배열을 문제의 조건식에 추가해서 작성하면 된다.

 

 

2번째 조건에서 a, b, c 모두 20 초과이면 무조건 return w(20, 20, 20)이기 때문에

dp[a][b][c]배열이 0일때  a, b, c의 범위가 20이하인 것을 추가해주면 된다.

 

 

 

<코드>

import java.io.IOException;
import java.util.Scanner;

public class Main {	
	
	static int dp[][][] = new int[21][21][21];
	
	public static void main(String[] args) throws IOException {
		
		Scanner sc = new Scanner(System.in);
		
		while(true) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();
			
			if(a == -1 && b == -1 && c == -1) {
				break;
			}
			
			System.out.println("w("+ a+", " +b+", "+c+") = " + w(a,b,c));
		}
	}
	
	static int w(int a, int b, int c) {
		
		if(range(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);
	}
	
	static boolean range(int a, int b, int c) {
		return 0 <= a && a<= 20 && 0 <= b && b<= 20 && 0 <= c && c<= 20;
	}
}

 

 

---

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

9184번: 신나는 함수 실행