[알고리즘 PS] 백준 9184번 신나는 함수 실행 자바 문제풀이

문제

해당 포스팅은 백준의 9184번 신나는 함수 실행 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

9184번: 신나는 함수 실행

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

문제 접근

이 문제는 조금 재밌는 문제였다.

 

보통 우리는 문제에 주어진 조건을 보고 분석하여 재귀 함수를 구현해야 하지만, 이 문제는 아예 재귀 함수를 주고 실행 시켜서 결과를 보여줘라는 문제로, 약간의 생각만 하면 되는 문제이다.

 

이번 문제의 핵심은 어떻게 재귀 함수의 성능을 향상 시킬 것이냐 에 관한 문제이다.

 

지난 재귀 호출의 이론에서 재귀 함수의 성능 향상을 위한 방법인 메모이제이션에 대해서 알아보았는데, 이 메모이제이션을 사용하면 문제를 해결할 수 있다.

해결법

이 재귀 함수를 그냥 실행 시킨다면 아마 최악의 경우 (20, 20, 20) 에서 4^(20 + 20 + 20) 의 재귀 함수의 call이 발생할 것이다.

 

그럼 대충 1,099,511,627,776 * 3 의 호출이 이루어져야 한다.

 

이 방법을 우리는 Memoization을 통해서 아주 획기적으로 줄일 수 있다.

 

결론은 이 문제의 큰 핵심은 메모이제이션을 사용할 줄 아냐 모르냐이다.

 

정답 코드

public class Main {
    static int[][][] arr = new int[51][51][51];
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        while(true) {
            int a = input.nextInt();
            int b = input.nextInt();
            int c = input.nextInt();

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

            if(a <= 0 || b <= 0 || c <= 0) {
                System.out.printf("w(%d, %d, %d) = %d \n", a, b, c, 1);
            }else {
                System.out.printf("w(%d, %d, %d) = %d \n", a, b, c, w(a, b, c));
            }
        }
    }

    private static int w(int a, int b, int c) {
        if(a <= 0 || b <= 0 || c <= 0) {
            return 1;
        }
        if(a > 20 || b > 20 || c > 20) {
            arr[a][b][c] = w(20, 20, 20);
            return arr[a][b][c];
        }

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

    }
}

---

 

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.