[백준] 9184 신나는 함수 실행 - 동적계획법(DP, Dynamic Programming) JAVA

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

코드설명

동적계획법과 메모이제이션을 활용합니다.

 

문제푸는 것은 어렵지 않았지만, 메모리초과가 발생하였습니다.

메모리 초과가 발생한 이유는, 매번의 테스트케이스마다 새로 cache = new int[51][51][51]과 같이 설정했기 때문입니다.

이렇게 설정한 이유는, 각 상태값들이 함수마다 모두 다르기에 값이 다르게 사용될 것이라 생각했는데, 생각해보면 같은 상태라면 다른 테스트케이스여도 모두 동일합니다.

 

그러므로 전역으로 cache 배열을 선언하도록 하고, 처음에는 [51][51][51]로 cache배열을 선언했었는데, 의사코드를 보면 20 20 20 이상일경우 무조건 w(20, 20, 20)을 선언하는 것을 볼 수 있었습니다.

그러므로, [21][21][21] 로 바꿔주고, ArrayIndexOutOfException 이 발생하지 않게 적절하게 함수의 위치를 수정해주면 됩니다.

특히, a > 20 || b> 20 ||  c> 20 부분에서 cache[a][b][c] 대신에 cache[20][20][20]으로 바꾸어서 처리하면 ArrayOutOfException이 손쉽게 해결됩니다. cache[20][20][20]인 이유는 a, b, c가 20 20 20 으로 호출될떄의 반환값을 의미하기에 그렇습니다.

 

처음에 푼 코드와 개선한 코드를 작성했습니다.

코드

개선한 코드입니다. 메모리를 낭비하지 않습니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	static int N, C, H, W, K, M, T, a, b, c;
	static int answer = 0;
	static int[] arr;
	static int[][][] cache;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		cache = new int[21][21][21];
		for(int i=0;i<21; i++) {
			for(int j=0; j<21; j++) {
				Arrays.fill(cache[i][j], -1);
			}
		}
		while(true) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			if(a == -1 && b == - 1 && c == -1) {
				return ;
			}
			
			System.out.println("w("+a+", "+b+", "+c+") = "+w(a, b, c));
		}
		
	}
	
	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 cache[20][20][20] = w(20, 20, 20);
		}
		if(cache[a][b][c] != -1) return cache[a][b][c];
		if(a < b && b < c) {
			return cache[a][b][c] = w(a, b, c-1) + w(a, b-1, c- 1) - w(a, b-1, c);
		}
		return cache[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);
	}
	
}

 

처음에 푼 코드입니다. 2000ms, 즉 2초가 걸립니다. 상당히 느린것을 알 수 있습니다.

cache 배열은 밖으로 빼서 처리하여 메모리초과를 벗어날 수 있습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	static int N, C, H, W, K, M, T, a, b, c;
	static int answer = 0;
	static int[] arr;
	static int[][][] cache;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		cache = new int[51][51][51];
		while(true) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			if(a == -1 && b == - 1 && c == -1) {
				return ;
			}
			
			
			for(int i=0;i<51; i++) {
				for(int j=0; j<51; j++) {
					Arrays.fill(cache[i][j], -1);
				}
			}
			
			System.out.println("w("+a+", "+b+", "+c+") = "+w(a, b, c));
		}
		
	}
	
	static int w(int a, int b, int c) {
		if(a <= 0 || b <= 0 || c <= 0) {
			return 1;
		}
		
		if(cache[a][b][c] != -1) return cache[a][b][c];
		
		if( a > 20 || b > 20 || c > 20) {
			return cache[a][b][c] = w(20, 20, 20);
		}
		if(a < b && b < c) {
			return cache[a][b][c] = w(a, b, c-1) + w(a, b-1, c- 1) - w(a, b-1, c);
		}
		return cache[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);
	}
	
}