[백준 1463번][Java] 1로 만들기

문제

 

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

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

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

 

---

 

풀이

 

1에서부터 N까지 올라가며

/3, /2,+1을 한 수에 +1값을 올리며 최솟값을 대입한다

 

---

 

코드

 

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

public class Main {
    public static int dp[] = new int[1000001]; //i의 범위만큼 -> find함수에서 i만큼만 선언해도 좋음
    
    public static void main(String args[]) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        
        find(N);
        System.out.println(dp[N]);
    }
    
    public static void find(int n) { //i를 반복문을 이용하여 i*3, i*2, i+1 dp를 채운다
        for(int i=1 ; i<=n ; i++) { //Bottom-Up 방식을 사용
            if(i*3 <= n)
                dp[i*3] = dp[i*3]==0 ? dp[i]+1 : min(dp[i*3], dp[i]+1);
            
            if(i*2 <= n)
                dp[i*2] = dp[i*2]==0 ? dp[i]+1 : min(dp[i*2], dp[i]+1);
            
            if(i+1 <= n)
                dp[i+1] = dp[i+1]==0 ? dp[i]+1 : min(dp[i+1], dp[i]+1);
        }
    }
    
    public static int min(int a, int b) { //Math.min() 메소드 이용가능
        if(a>b)
            return b;
        else
            return a;
    }
}