2022.04.05 100일차!

백준 1463번 (1로 만들기)

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

나의 풀이

1. 경우의 수
   1 => 0
   2 => 1
   3 => 1
   4 => 2
   5 => 3
   6 => 2
   7 => 3
   8 => 3
   9 => 2
   10 => 3
2. 예외 - 10인 경우 2로 나누는 것이 아닌 1을 빼는 경우가 가장 최소
3. 큰 수로 나누는 경우부터 접근, 최소값 비교하기

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

public class Main {
    static long[] 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 long[n + 1];

        for (int i = 2; i <= n; i++) {
            if (i % 6 == 0) {
                dp[i] = Math.min(dp[i / 3] + 1, Math.min(dp[i / 2] + 1, dp[i - 1] + 1));
            }
            else if (i % 3 == 0) {
                dp[i] = Math.min(dp[i / 3] + 1, dp[i - 1] + 1);
            }
            else if (i % 2 == 0) {
                dp[i] = Math.min(dp[i / 2] + 1, dp[i - 1] + 1);
            }
            else {
                dp[i] = dp[i - 1] + 1;
            }
        }

        System.out.println(dp[n]);
    }
}

생각하기

• DP 문제 풀이 연습