JAVA 백준 문제풀이 (22) 9184: 신나는 함수 실행

 

 

 

 

메모이제이션(Memoization)에 대해 알고 있다면 아주 쉽게 풀 수 있는 문제고, 메모이제이션을 모른다면 아래에서 피보나치 수열 예제를 보고 속성으로 배우도록 하자.

메모이제이션을 알고 재귀를 사용하는 것과 모르고 사용하는 것의 차이는 엄청나다.

 

 

https://7357.tistory.com/105?category=1065986 

피보나치 수열에서 n번째 수를 쉽게 구하는 세가지 방법. (Feat. Java)

 

 

전혀 어려운 개념이 아니니 걱정할 것 없다.

재귀가 반복적으로 같은 연산을 수행하기 때문에 성능이 안 좋다는 점을 이용해서 같은 연산 시에는 이전에 연산한 결과를 리턴함으로써 성능을 끌어올린 것이다.

 

정말 설명할 것도 없이 쉬운 문제이기 때문에 바로 답으로 넘어가자.

 

 

 

 

 

 

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


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        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) { System.exit(0); }
            System.out.printf("w(%d, %d, %d) = %d%n", a, b, c, w(a,b,c));
        }
    }

    // return 값을 저장할 배열
    static Integer[][][] memo = new Integer[51][51][51];
    public static Integer w(int a, int b, int c) {
        if ( a<=0 || b<=0 || c<=0 ) { return 1; }
        if (memo[a][b][c] != null) { return memo[a][b][c]; }
        if ( a>20 || b>20 || c> 20) { return memo[a][b][c] = w(20, 20, 20); }
        if ( a<b && b<c) { return memo[a][b][c] = w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c); }
        return memo[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);
    }
}

기저 조건, 즉 abc 중 하나가 음수인 경우는 무조건 1을 리턴하기 때문에 저장할 필요가 없다.

나머지는 모조리 저장해놓고 계속해서 우려먹으면 된다.