[BAEKJOON] 백준 DP 1463 :: 1로 만들기 JAVA

 

💬  문제 설명

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

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

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

 

🔨  입출력 예

입력 

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

 

출력

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

 

예제 입력 1)

2

 

예제 출력 1)

1

 

예제 입력 2)

10

 

예제 출력 2)

3

​

Hint ) 10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

 

 

​

💻  Main.java

• DP를 이용해 문제를 푼다. 각각의 연산의 최솟값을 dy[n]에 저장한다.
• dy[0] = 0, dy[1] =0 이다.
• 모든 값은 1로 뺐을 때의 값이 있기 때문에, 1로 뺐을 때의 값을 기본으로 잡아주자.
• 2로 나누어 질때, 3으로 나누어 질때의 최솟값을 계산한다. 
• 6으로 나누어 떨어질 때, 2와 3으로 나눴을 때와 1을 뺐을 때를 모두 비교해준다.

/* 백준 DP - 1463 :: 1로 만들 */
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] dy = new int[n + 1];
		
		for(int i = 2; i <= n; i++) {
			dy[i] = dy[i - 1] + 1;
			
			if(i % 6 == 0) {
				dy[i] = Math.min(dy[i / 3] + 1, Math.min(dy[i / 2] + 1, dy[i]));
			}
			else if(i % 3 == 0) {
				dy[i] = Math.min(dy[i / 3] + 1, dy[i]);
			}
			else if(i % 2 == 0) {
				dy[i] = Math.min(dy[i / 2] + 1, dy[i]);
			}
		}
		
		System.out.println(dy[n]);
		sc.close();
	}
}