[백준] 9184번 : 신나는 함수 실행 - 자바[Java]

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

9184번: 신나는 함수 실행

풀이

반복적인 재귀 호출을 방지하기 위해, w(a, b, c)의 반환값을 저장하는 3차원 dp 배열을 사용한다.

이 때 -50 ≤ a, b, c ≤ 50 이므로, 인덱스를 0부터 100까지 사용하기 위해 배열의 크기를 101x101x101만큼 할당하여 w(a, b, c)의 반환값을 dp[a+50][b+50][c+50]에 저장한다.

 

 

로직

1. int형 3차원 배열 dp를 선언하고, 크기를 101x101x101만큼 할당한다.

2. while문을 사용하여 a, b, c를 입력받는다. (a,b,c) 가 (-1, -1, -1)인 경우 반복문을 탈출한다.

3. a, b, c 모두 50씩 더한 후 w(a, b, c)를 호출한다.

4. 출력 형식에 맞게 출력한다.

int w(int a, int b, int c)

    public 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) {
            dp[a][b][c] = 1;
        }

        else if (a > 70 || b > 70 || c > 70) {
            dp[a][b][c] = w(70, 70, 70);
        }

        else if (a < b && b < c) {
            dp[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
        }
        else {
            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);
        }

        return dp[a][b][c];
    }

• dp[a][b][c]가 0이 아닌 경우, 이미 반환값을 구한 것이므로 바로 dp[a][b][c]를 리턴한다.
• 문제에 나와 있는대로 함수를 구현한다. 각 경우마다 반환값을 구하고 그 값을 dp[a][b][c]에 저장한 다음 리턴한다.

코드

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

    static int[][][] dp = new int[101][101][101];

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st;

        while(true) {
            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;

            bw.write("w(" + a + ", " + b + ", " + c + ") = ");
            a += 50;
            b += 50;
            c += 50;
            bw.write(w(a,b,c) + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    public 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) {
            dp[a][b][c] = 1;
        }

        else if (a > 70 || b > 70 || c > 70) {
            dp[a][b][c] = w(70, 70, 70);
        }

        else if (a < b && b < c) {
            dp[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
        }
        else {
            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);
        }

        return dp[a][b][c];
    }

}

 

---

다른 풀이 2

• if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns: 1 이므로 a나 b나 c가 음수인 경우는 따로 배열에 저장할 필요가 없다.
• if a > 20 or b > 20 or c > 20, then w(a, b, c) returns: w(20, 20, 20)이므로 배열의 인덱스가 20보다 큰 경우는 따로 배열에 저장할 필요가 없다.

코드

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

    static int[][][] dp = new int[21][21][21];

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st;

        while(true) {
            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;

            bw.write("w(" + a + ", " + b + ", " + c + ") = ");
            bw.write(w(a,b,c) + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    public static int w(int a, int b, int c) {

        //인덱스가 배열의 범위를 벗어나지 않고, 메모이제이션이 되어있는 경우
        if (checkIndexRange(a,b,c) && dp[a][b][c] != 0)
            return dp[a][b][c];

        if (a <= 0 || b <= 0 || c <= 0) {
            return 1;
        }

        else if (a > 20 || b > 20 || c > 20) {
            return w(20, 20, 20);
        }

        else if (a < b && b < c) {
            dp[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
        }
        else {
            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);
        }

        return dp[a][b][c];
    }

    public static boolean checkIndexRange(int a, int b, int c) {
        if (a >= 0 && a <= 20 && b >= 0 && b <= 20 && c >= 0 && c <= 20)
            return true;
        else return false;
    }

}

 

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