[goormlevel/Java] 최소 연산 횟수2

-Code

import java.io.*;
import java.util.*;

class Main {
	static Map<Long, Long> numCntMap = new HashMap<>();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        long n = Long.parseLong(br.readLine());
        System.out.println(getMinCnt(n));
    }

    private static long getMinCnt(long num) {
        // 1보다 작으면 0 반환
        if (num <= 1) return 0;

        if (numCntMap.containsKey(num)) return numCntMap.get(num);
        // 2와 3으로 나눌때 각각 필요한 횟수 구하기
        long modPath2 = num % 2 + 1 + getMinCnt(num / 2);
        long modPath3 = num % 3 + 1 + getMinCnt(num / 3);
        // 더 작은 숫자의 횟수 계산 및 추가
        long res = Math.min(modPath2, modPath3);
        numCntMap.put(num, res);
        return res;
    }
}

처음에 최소여서 BFS로 하려다가 이러면 시간 초과가 발생하고, while로 다시 짜보려니 n의 값을 변동하는데 2로나 3으로 나누는 과정에서 선택을 해야해서 진행이 안됐습니다.

그래서 힌트를 찾아보니 1로 빼야할 횟수를 가지고 재귀를 이용하고 map을 통해서 메모리를 아끼라는 것이었습니다. 이후 나머지 연산으로 1로 빼는 횟수를 구하고 다음으로 넘어가니 1을 더해서 빼고 나누는 횟수를 구했습니다.

그 후에 이전 계산 값을 구하는 부분을 재귀로 처리하는데 1이하면 나눌 값이 없으므로 0, map에 존재하면 그 갯수를 가져와서 더해주면 해결이 되는 문제였습니다.

처음 접근 방법에 대해서 최근 혹은 자주 사용하는 방법을 먼저 생각해 진행이 안되는 부분에 대해서 아쉬웠습니다.