[백준] 자바 Java, 1463번: 동적 계획법 > 1로 만들기

 

1463번: 1로 만들기

---

문제

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

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

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다.

연산을 사용하는 횟수의 최솟값을 출력하시오.

 

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

 

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

 

알고리즘 분류

• 다이나믹 프로그래밍

 

나의 풀이

참고)

[알고리즘-JAVA] 백준 알고리즘 1463번 - 1로 만들기

• Bottom-up 방식 사용

나누기 3 > 나누기 2 > 빼기 1 순서대로 푸는 방식은 X, 반례가 존재한다,

10 같은 경우 나누기 2보다 빼기 1을 먼저 수행하는 방식이 연산 횟수를 1회 줄일 수 있다.

 

그렇기 때문에 3가지 연산의 최소 연산 수를 모두 비교하는 것이 필요하다.

package level15_dynamicProgramming;

import java.util.Scanner;

// 백준 1463번 문제] 1로 만들기
public class Backjoon1463 {
    static int[] dp;

    public static void main(String[] args) {
        //입력start
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        dp = new int[n + 1]; // 숫자 헷갈리지 않게 1부터 n까지 대입하기 위해 n+1 함
        //입력end

        //dp초기화
        dp[0] = dp[1] = 0;

        for(int i=2; i<=n; i++) {
            // -1 연산을 수행할 경우
            dp[i] = dp[i-1] + 1; // +1은 연산을 수행한 카운터를 하나 올려줌

            if(i%3 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 3] + 1); // 나누기 3 연산 수행할 경우와 -1 연산 수행한 경우 비교
            }
            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 2] + 1); // 나누기 3 연산 수행할 경우와 -1 연산 수행한 경우 비교
            }
        }

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

}

 

결과