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

[문제 바로 가기] - 신나는 함수 실행

유형 : 재귀 + dp

💡 접근 방식

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);

else 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를 사용해서 값을 저장하며 계산해야 시간을 줄일 수 있다.

1. a, b, c 중 하나라도 0 이하면 1
2. a, b, c 중 하나라도 20보다 크면 w(20, 20, 20)

위 조건으로 인해 dp 배열의 크기는 a, b, c 각각 21이 된다.

• dp[a][b][c]가 0이 아닐 경우 dp[a][b][c]를 return
• 0일 경우에는 조건에 따라 연산을 수행 => dp 배열에 값 저장

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * 백준 9184번 신나는 함수 실행
 * - 재귀 + dp
 */

public class Main {
	public static int dp[][][];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		dp = new int[21][21][21];
		
		while (true) {
			String str = br.readLine();
			
			if (str.equals("-1 -1 -1")) break;
			
			st = new StringTokenizer(str);
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			sb.append("w(" + a + ", " + b + ", " + c + ") = " + w(a, b, c) + "\n");
		}
		
		System.out.println(sb);
	}
	
	public 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 (dp[a][b][c] != 0) return dp[a][b][c];
		
		if (a < b && b < c) dp[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
		else 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);
		
		return dp[a][b][c];
	}
}