02 Mar 2024

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

9184

풀이 방법

문제에서 주어진 재귀 함수를 구현하는 문제이다. psuedo코드를 언어에 맞게 최적화하는 것 뿐만 아니라 이미 계산된 값은 다시 계산할 필요 없도록 Memoization을 사용해야 하는 문제이다.

a, b, c가 주어지고 문제에서 a>20 or b>20 or c>20 then return 1이기 때문에 값을 저장할 3차원 배열 w_store를 21개씩 만들어줬다. 그리고 값의 수정이력을 알기 위해 배열의 전체 요소를 -1로 초기화 한다.

재귀함수를 반복할 때 이미 저장되어있는 수라면 w_store[a][b][c]를 return하고, 그렇지 않다면 계산을 하도록 만들면 된다.

풀이 코드

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

public class BOJ_9184_신나는_함수_실행 {
	static int[][][] w_store;
	public static void main(String[] args) throws Exception { 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		w_store = new int[21][21][21];
		
		for(int i=0; i<21; ++i) {
			for(int j=0; j<21; ++j) {
				for(int k=0; k<21; ++k) {
					w_store[i][j][k] = -1;					
				}
			}
		}
		
		while(true) {
			st = new StringTokenizer(br.readLine());
			int[] ns = new int[3];
			boolean flag = true;
			
			for(int i=0; i<3; ++i) {
				int input = Integer.parseInt(st.nextToken());
				if(input != -1) flag = false;
				ns[i] = input;
			}
			
			if(flag) break;
			
			int res = w(ns[0], ns[1], ns[2]);
			sb.append("w("+ns[0]+", "+ns[1]+", "+ns[2]+") = "+res+"\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) return w(20, 20, 20);
		
		if(w_store[a][b][c] != -1) return w_store[a][b][c];
		
		if(a<b && b<c) return w_store[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
		else return w_store[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);
	}
}

Thank You For Reading

점점 강해지고 있습니다.