[9184] 신나는 함수 실행

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

문제 설명

---

재귀 함수를 사용해 정의된 함수 w(a, b, c) 를 효율적으로 계산하는 문제를 해결한 코드이다.
해당 함수는 다음과 같은 규칙을 따른다.

1. 기저 조건:
   • 만약 a, b, c 중 하나라도 0 이하이면, w(a, b, c) = 1이다.
2. 상한 조건:
   • 만약 a, b, c 중 하나라도 20보다 크면, w(a, b, c) = w(20, 20, 20)로 계산한다.
3. 특수 조건:
   • 만약 a < b 그리고 b < c인 경우,
     w(a, b, c) = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)로 계산한다.
4. 일반 조건:
   • 위의 조건에 해당하지 않는 경우,
     w(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)로 계산한다.

입력은 여러 개의 (a, b, c) 쌍으로 주어지며, (-1, -1, -1)이 입력되면 프로그램이 종료된다. 출력은 각각의 입력에 대해
w(a, b, c) = 결과값의 형식으로 결과를 보여준다.

문제 풀이

---

1. 입력 처리 및 종료 조건
   • BufferedReader와 StringTokenizer를 사용하여 입력을 한 줄씩 읽는다.
   • 입력된 a, b, c 값이 모두 -1이면 while 루프를 종료한다.
   • 각 입력에 대해 결과를 StringBuilder에 누적하여 마지막에 출력한다.
2. 메모이제이션을 위한 dp 배열
   • static int[][][] dp = new int[21][21][21];
     크기가 21×21×21 인 3차원 배열을 미리 선언해, a, b, c가 0 이상 20 이하인 경우의 결과를 저장한다.
   • rangeCheck 메소드를 통해 입력 값이 dp 배열의 범위 내에 있는지 확인한다.
   • 이미 계산된 값(0이 아닌 값)이 있으면, 재귀 호출을 피하기 위해 바로 반환한다.
3. 재귀 함수 calcw(a, b, c)
   • 메모이제이션 검사:
     rangeCheck(a, b, c)로 범위 내 확인 후, dp[a][b][c]가 이미 계산되었으면 그 값을 반환한다.
   • 기저 조건 처리:
     • a, b, c 중 하나라도 0 이하인 경우 1을 반환한다.
   • 상한 조건 처리:
     • 만약 a, b, c 중 하나라도 20보다 크면,
       w(a, b, c) = w(20, 20, 20)으로 계산하여, 그 값을 dp[20][20][20]에 저장 후 반환한다.
   • 특수 조건 (a < b < c):
     • 이 조건에 해당하면,
       calcw(a, b, c-1) + calcw(a, b-1, c-1) - calcw(a, b-1, c)의 결과를 dp 배열에 저장하고 반환한다.
   • 일반 조건:
     • 나머지 경우에는,
       calcw(a-1, b, c) + calcw(a-1, b-1, c) + calcw(a-1, b, c-1) - calcw(a-1, b-1, c-1)를 계산하여 dp 배열에 저장 후 반환한다.
4. 메인 메소드
   • 입력을 반복적으로 처리하면서 각 (a, b, c) 쌍에 대해 calcw(a, b, c)를 호출하여 결과를 구하고, 지정된 형식(w(a, b, c) = 결과값)으로 출력 문자열을 구성한다.
   • 모든 입력 처리가 끝나면 누적된 결과를 출력한다.

전체 코드

---

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

public class BOJ9144 {
    static int a,b,c;
    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());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            if (a == -1 && b == -1 && c == -1) {
                break;
            }
            sb.append("w(").append(a).append(", ").append(b).append(", ").append(c).append(") = ").append(calcw(a,b,c)).append("\n");
        }
        System.out.println(sb);
    }

    static int calcw(int a, int b, int c) {
        if (rangeCheck(a, b, c) && 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] = calcw(20, 20, 20);
        } 
        if (a < b && b < c) {
            return dp[a][b][c] = calcw(a, b, c-1) + calcw(a, b-1, c-1) - calcw(a, b-1, c);
        } 
        return dp[a][b][c] = calcw(a-1, b, c) + calcw(a-1, b-1, c) + calcw(a-1, b, c-1) - calcw(a-1, b-1, c-1);
    }

    static boolean rangeCheck(int a, int b, int c) {
        return 0 <= a && a <= 20 && 0 <= b && b <= 20 && 0 <= c && c <= 20; 
    }
}

소감

---

dp에 더 익숙해질 필요가 있어서 다시 쉬운 문제부터 풀어보고자 했다. 해당 문제는 필요한 함수가 이미 구현돼 있어서 몇 가지 조건과 수정만 추가하면 됐다! 다음 문제는 직접 점화식을 고민해볼 수 있도록 골라야겠다.