[알고리즘] 백준 9184 신나는 함수 실행 Java

문제 정보

플랫폼 : 백준
분류 : Dynamic Programming (동적 프로그래밍)
난이도 : 실버 2
링크 : https://www.acmicpc.net/problem/9184

시간제한 및 메모리 제한 검증

O(n) 풀이
자료형 : 최대 1048576, int

풀이

1. 배열의 크기는 21x21x21 이면 충분하다! 문제의 조건에서
   if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns: 1
if a > 20 or b > 20 or c > 20, then w(a, b, c) returns: w(20, 20, 20)
   이 존재하기 때문에 입력 데이터 (-50 ≤ a, b, c ≤ 50)에서
   음수 및 21 이상은 고려 할 필요가 없다.

2. 아래 조건을 위해, 배열에서 0이 들어가는 부분은 1로 초기화 한다.
   if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns: 1
   

3. 아래 조건을 위해, 배열을 3중 for문을 통해 채워준다.
   if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

for(int i = 1; i <= 20; i++) 
	for(int j = 1; j <= 20; j++)
		for(int k = 1; k <= 20; k++) {
			if(i < j && j < k) {
				map[i][j][k] = map[i][j][k-1] + map[i][j-1][k-1] - map[i][j-1][k];
				continue;
			}
			map[i][j][k] = map[i-1][j][k] + map[i-1][j-1][k] + map[i-1][j][k-1] - map[i-1][j-1][k-1];					
		}

3번에서 위과 같이 3중 for문을 써도 무관할지 궁금할 수도 있다. (나도 그랬다.) 예시를 통해 증명해보자.

i < j && j < k 에서 i = 1, j = 2, k = 3이라고 예를 들어보자.

map[i][j][k] = map[i][j][k-1] + map[i][j-1][k-1] - map[i][j-1][k];를 채워보면 다음과 같다.

map[1][2][3] = map[1][2][2] + map[1][1][2] - map[1][1][3]
위 식에서 map[1][2][3], map[1][1][2], map[1][1][3] 은 i, j, k = 1, 2, 3이 충족되기 전에 채워지고, 이후에 바뀔 일이 없으므로 3중 for문을 위와 같이 작성해도 무관하다.

이후에는 입력을 받으면서 출력해주면 되는 간단한 문제이다.

코드

import java.util.*;
import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int[][][] map = new int[21][21][21];
		
		for(int i = 0; i <= 20; i++)
			for(int j = 0; j <= 20; j++) {
				map[0][i][j] = 1;
				map[i][0][j] = 1;
				map[i][j][0] = 1;
			}
		
		for(int i = 1; i <= 20; i++) 
			for(int j = 1; j <= 20; j++)
				for(int k = 1; k <= 20; k++) {
					if(i < j && j < k) {
						map[i][j][k] = map[i][j][k-1] + map[i][j-1][k-1] - map[i][j-1][k];
						continue;
					}
					map[i][j][k] = map[i-1][j][k] + map[i-1][j-1][k] + map[i-1][j][k-1] - map[i-1][j-1][k-1];					
				}
		String[] input;
		while(true) {
			input = br.readLine().split(" ");
			int a = stoi(input[0]);
			int b = stoi(input[1]);
			int c = stoi(input[2]);
            int ret = 0;
			if(a == -1 && b == -1 && c == -1) {
				System.out.println(sb);
				return;
			}else if(a <= 0 || b <= 0 || c <= 0) ret = 1;
			 else if(a > 20 || b > 20 || c > 20) ret = map[20][20][20];
             else ret = map[a][b][c];
             sb.append("w(").append(a).append(", ").append(b).append(", ").append(c).append(") = ").append(ret).append("\n");
		}
		
	}
	public static int stoi(String str) {return Integer.parseInt(str);}
}

더 많은 정답 코드

블로그를 쓰기 이전에 풀어본 문제들이 많다. 해설강의는 없지만, 백준 문제의 풀이 코드가 필요한 경우 이곳을 클릭하여 소스코드를 참조해보도록 하자. 단, 코드만 복사-붙여넣기 하는것은 본인에게 결코 도움이 되지 않는다. 반드시 먼저 생각해보고, 막히는 경우에 참고하고 왜 이렇게 코드가 작성됐는지를 다시 한 번 생각해보는 습관을 들이자.