21.09.21 기록

백준 알고리즘 1463 풀이

🎆나의 오답(시간초과)

-이전 문제들의 해설에서 사용했던 dp 로직을 생각하며 거의 처음으로 제대로 된 DP 풀이를 해본 것 같은데 시간초과로 실패했다.
-해설을 보니 잘못된 로직은 아닌 것 같은데.. 정말 시간초과로 풀지 못한 듯 하다.

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

public class B1463 {
    public static Integer[] dp;

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

        int N = Integer.parseInt(br.readLine());
        dp = new Integer[N+1];

        dp[0] = 0;
        dp[1] = 0;

        System.out.println(find(N));
    }

    public static int find(int N) {

        if(dp[N] == null) {
            if(N % 6 == 0) {
                return dp[N] = Math.min(find(N-1), Math.min(find(N/2), find(N/3))) + 1;
            }

            else if(N % 3 == 0) {
               return dp[N] = Math.min(find(N-1), find(N/3)) + 1;
            }

            else if(N % 2 == 0) {
                return dp[N] = Math.min(find(N-1), find(N/2)) + 1;
            }

            else return dp[N] = find(N-1) + 1;
        }

        return dp[N];
    }
}

🎆해설(메모리 14.2MB, 시간 136ms로 통과)

-해설의 첫 번째 알고리즘 접근 방법은 내가 풀이한 로직과 같아서 두 번째 알고리즘 접근 방법을 가져왔다.
-Integer[] 배열을 사용하는 대신 누적된 count 값을 return 하는 로직이다.

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

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

        int N = Integer.parseInt(br.readLine());
        System.out.println(find(N, 0));
    }

    public static int find(int N, int cnt) {
        if(N < 2) {
            return cnt;
        }

        return Math.min( find(N/2,cnt+1+(N%2)), find(N/3, cnt+1+(N%3)));
    }
}