[백준] 9184. 신나는 함수 실행

문제 링크

[백준] 9184. 신나는 함수 실행

풀이 과정

DP 문제입니다. 문제의 입력 제한이 없기 때문에, 입력을 하나씩 처리할 때마다, dp 배열에 저장되는 요소들이 많아집니다.

static int w(int a, int b, int c) {
    if (dp[a][b][c] != 0) return dp[a][b][c];

    if (a <= 50 || b <= 50 || c <= 50) return 1;
    if (a > 70 || b > 70 || c > 70) return dp[a][b][c] = w(70, 70, 70);
    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);
}

하나의 조건을 추가하고 문제의 네 가지 조건을 그대로 옮겨 적었습니다.

• 맨 위 조건은 a, b, c 인덱스에 메모되었던(이미 구했던) 이력이 있으면 그걸 리턴함으로써 시간을 단축시킵니다.
• 나머지 조건들은 리턴과 동시에 메모를 하는 과정을 나타냅니다. 나중에 다시 방문했을 때 빠르게 값을 가져다 쓰기 위함입니다.

코드

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

public class Main {
    static int[][][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        dp = new int[101][101][101];

        while (true) {
            int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int a = input[0];
            int b = input[1];
            int c = input[2];

            if (a == -1 && b == -1 && c == -1) break;

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

        System.out.println(sb);
    }

    static int w(int a, int b, int c) {
        if (dp[a][b][c] != 0) return dp[a][b][c];

        if (a <= 50 || b <= 50 || c <= 50) return 1;
        if (a > 70 || b > 70 || c > 70) return dp[a][b][c] = w(70, 70, 70);
        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);
    }
}