/ BOJ

BOJ_9184_신나는함수실행_JAVA

문제 : 신나는함수실행

링크 : BOJ_9184_신나는함수실행

접근 방식

인자값을 3개를 사용하는 재귀함수의 수행속도를 줄이기 위해, DP, 메모이제이션 기법을 사용해야 하는 문제이다.

풀이 방법

DP란 무엇일까?

동적계획법이라고도 부른다. 하지만 이 글을 쓰는 지금도 DP에 개념에 대해 제대로 알지 못하겠다.

DP의 조건은 3가지가 있다.

  1. 먼저 큰 문제가 작은 문제로 쪼개질 수 있는가.
  2. 작은문제들의 해로 큰 문제의 해를 구할 수 있는가.
  3. 그리고, 이 해들이 중복되는가.

이 3가지 조건이 충족되면 DP를 적용할 수 있다고 한다.

하지만 이러한 내용은 내게 너무 낮설고 적용하기도 어려웠다.

나는 이 문제를 풀면서 어떻게 DP를 사용하는 지에만 집중했다.

결론은 이것이다. 재귀를 통해 호출되는 함수의 결과를 기억해두고, 재귀를 통해 호출하는 함수가 기억되어있는 함수와 같다면, 재귀를 호출하지 않고 기억되어있는 함수의 값을 리턴한다.

메모이제이션은 이것을 말하는 것이다. ‘기억’하는 것.

그렇기 때문에, 3개의 인자값을 받는 이 재귀함수의 파라미터 a,b,c. 이 값을 배열로 선언해 0으로 초기화 해두고, 호출된 함수의 위치에 결과값을 저장했다. 그 후 같은 인자값을 사용하는 함수가 재귀호출될 경우, 그 함수는 추가적인 작업 없이 저장되어있는 결과값을 리턴하고 종료된다.

이번 문제에서는 DP에 대해 이정도까지밖에 이해하지 못했다. 몇몇 문제를 더 풀어보며 이해력을 늘려야 한다.

소스 코드


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

public class BOJ_9184_신나는함수실행 {

	static int[][][] dp;
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		dp = new int[21][21][21];
		while(true) {
			st = new StringTokenizer(in.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;
			}
			long n = w(a,b,c);

			sb.append(String.format("w(%d, %d, %d) = %d\n",a,b,c, n));
		}
		System.out.print(sb);
	}

	public static int w(int a, int b, int c) {

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

		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);
			return dp[a][b][c];
		}
		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];

	}

}