9184 번 문제 풀이

using Java 11

9184 문제 보기

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

public class boj9184 {
	public static int[][][] dp = new int[21][21][21];
	
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		while(true) {
			StringTokenizer st = new StringTokenizer(br.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;
			}
			sb.append("w(" + a + ", " + b + ", " + c + ") = ").append(w(a,b,c)).append("\n");
		}
		System.out.println(sb);
	}
	
	public static int w(int a, int b, int c) {
		if(a >= 0 && a <= 20 && b >= 0 && b <= 20 && c >= 0 && c <= 20) {
			if(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) {
			return dp[20][20][20] = w(20, 20, 20);
		}
		
		if (a < b && b < c) {
			return 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] = 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를 정복해보자
재귀를 메모이제이션으로 조금 수정해서 풀었다. 기억에 남는 어려움은 없었던 거 같다. 그냥 나는 함수 실행이 신나진 않았다...

📍핵심은 범위
범위를 줄여서 삼차원 배열의 크기를 작게 만들어 주는게 포인트다. 직관적으로 조건문 사용해서 걸러 내니 무리 없이 바른 출력이 나왔다.

(참고: https://st-lab.tistory.com/190)