[BaekJoon] 9184번 신나는 함수 실행 (Java) 문제 풀이 [Sliver 2]

문제

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

9184번: 신나는 함수 실행

 

어떻게 풀 것인가?

우선적으로 DP에 대한 풀이를 떠올렸다. 하지만 DP 즉 점화식으로 풀려고하니 좀 머리가 아프고 직관적이지 못하다는 생각이 들었다.

 

그래서 HashMap을 이용한 메모제이션 기법을 이용하기로 생각했다.

 

문제에서 주어진 재귀함수는 중복 계산이 많이 발생하므로, 메모이제이션(Memoization)을 사용하여 중복 계산을 피할 수 있다. 메모이제이션은 한 번 계산한 값을 저장해두고 필요할 때마다 재사용하는 기법이다.

 

이러한 기법을 이용하여 코드가 좀 더 직관적이라고 생각해서 풀이하였다.

 

풀면서 놓쳤던점

크게 놓친 부분은 없었으나, 풀이에 대한 고민은 조금 많았다. 어떠한 접근방법이 옳을까에 대해서 고민을 좀 많이했었다.

 

이 문제를 통해 얻어갈 것

HashMap을 이용한 메모제이션

 

내 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
import java.util.StringTokenizer;

public class Main {
    private static final Map<String, Integer> memoizationMap = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        while (true) {
            String str = br.readLine();
            if (Objects.equals(str, "-1 -1 -1")) break;
            StringTokenizer st = new StringTokenizer(str);
            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());
            int num3 = Integer.parseInt(st.nextToken());
            sb.append("w(").append(num1).append(", ").append(num2).append(", ").append(num3).append(") = ").append(w(num1, num2, num3)).append("\n");
        }
        System.out.println(sb);
    }

    public static int w(int a, int b, int c) {
        String key = a + "," + b + "," + c;

        if (memoizationMap.containsKey(key)) {
            return memoizationMap.get(key);
        }

        int result;

        if (a <= 0 || b <= 0 || c <= 0) {
            result = 1;
        } else if (a > 20 || b > 20 || c > 20) {
            result = w(20, 20, 20);
        } else if (a < b && b < c) {
            result = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
        } else {
            result = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
        }

        memoizationMap.put(key, result);
        return result;
    }
}

 

참고

X