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

문제

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

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

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

입력

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

출력

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

 

 

 

드디어 DP part로 넘어왔다

2학년 2학기 겨울방학때 if문 for문 배열 문자열 조금 끄적인 뒤로 

3학년 1학기는 열심히 학업에 집중하였고

3학년 1학기 여름방학에는 토익에 자격증공부에 코딩을 제대로 할 시간이 없었다 (물론 핑계인것은 안다..)

3학년 2학기는 학점은 좋지 못했지만 너무 바쁜 날들이였다 

이번 겨울방학때는 코딩을 열심히 해보자는 다짐과 함께 

그리디, 자료구조, 수학 part를 넘어 DP part로 넘어왔다

DP는 사실 살짝 겁이 나는 part다 

3학년 2학기 알고리즘 시간에 과제로 받은 문제에서 dp니 분할정복이니.. 이런 문제들은 죄다 어려운 문제였기 때문이다

그래도 마음을 다 잡고 시작해보자

 

dp 개념은 정리가 되었고

 

이 문제는 딱봐도 dp 기본문제인것 같았다 . 그런데 정답률을 보니 31퍼..?

아마 dp를 모르고 접근하면 시간초과가 나나 보다

 

나는 이 문제를 bottom-up 방식으로 풀었다

bottom-up 방식으로 이 문제를 풀기 위한 조건들은 간단하다

 

 

1. 입력값으로 최댓값은 1000000이므로 크기가 1000001인 dp배열을 만든다

2. 1을 1로 만드는건 계산횟수가 0이므로 dp[1]=0으로 해준다

3. 2부터는 점화식을 세운다 

point

어떤수 n이 1이 되기 위한 최소 횟수는 

1.n-1이 1이 되기 위한 최소 횟수 +1이 될수도 있고  

2. n이 2으로 나누어 떨어지는 수이면 n/2이 1이 되기 위한 최소 횟수+1이 될수도 있고

3. n이 3으로도 나누어 떨어지는 수이면 n/3이 1이 되기 위한 최소 횟수+1이 될수도 있다

 

셋다 될수도 있다고? 그럼 언제 되는거야?

 

이건 간단하다 1,2,3중에 최솟값이 바로 d[n]->n을 1로 만들기 위한 최소 횟수이다 

이렇게 점화식을 세우면 코드 구현은 간단하다 

 

import java.util.*;
public class Main {
    public static int []dp=new int[1000001];
    public  static  void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        System.out.println(DP(n));
    }

    public static int DP(int n){
        dp[1]=0;
        for(int i=2;i<=n;i++){
            dp[i]=dp[i-1]+1; 
            if(i%2==0 && dp[i]>dp[i/2]+1){
                dp[i]=dp[i/2]+1;
            }
            if(i%3==0 && dp[i]>dp[i/3]+1){
                dp[i]=dp[i/3]+1;
            }
        }
        return dp[n];
    }
}