백준 1463_1로 만들기_JAVA

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

1463번: 1로 만들기

시간 초과

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int count = 0;

        while (N != 1) {
            count++;
            if ((N - 1) % 3 == 0) {
                N--;
                continue;
            } else if (N % 3 == 0) {
                N = N / 3;
                continue;
            } else if (N % 2 == 0) {
                N = N / 2;
                continue;
            }
        }

        System.out.print(count);

    }
}

 

정답

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[N + 1]; // DP array (각 숫자를 1로 만드는 데 필요한 최소 연산 횟수)
        for (int i = 2; i < N + 1; i++) {
            dp[i] = dp[i - 1] + 1; // 1을 빼는 경우를 기본 값으로 둔다
            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 2] + 1); // 2로 나누는 경우랑 1을 뺀 경우랑 비교하여 작은 걸 대입
            }
            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
            }
        }

        System.out.print(dp[N]);
    }
}

회고

- 무식하게 그냥 구현했더니 시간초과가 났다.

- 처음에 방식을 생각을 못해 블로그를 참고하고 해결했다.

- dp에 조금 약한 것 같다.