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

#1463 1로 만들기

난이도 : 실버 3

유형 : DP

1463번: 1로 만들기

▸ 문제

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

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

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

▸ 입력

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

▸ 출력

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

 

문제 풀이  

DP문제로 바텀업, 탑다운 어떤 방식으로 접근해도 상관없다. 정수 N → 1로 향하는 문제이다보니 자연스레 나는 탑다운 형식으로 접근했다. 

 

설계

1. 현재 숫자 num에 세 가지 연산을 실행한다.
   1. num이 3으로 나누어지는 수라면 3으로 나눈 후 카운트 +1 해준다. if(num%3==0) 
   2. num이 2으로 나누어지는 수라면 2으로 나눈 후 카운트 +1 해준다. if(num%2==0) 
   3. num을 -1로 빼준 후 카운트 +1 해준다. 
2. num이 1이 된다면 연산 횟수의 최솟값(ans)을 구해준다.
3. 만약 연산 과정시 현재 구한 최솟값(ans)을 초과할 경우 해당 연산은 종료시킨다 (중복된 연산 제거함으로써 시간초과 방지)

 

풀이 코드  (Top-down)

import java.io.*;

public class Main {
	
	static int ans = Integer.MAX_VALUE;
	public static void main(String[] args) throws  IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		toOne(n,0);
		System.out.println(ans);
	}
	
	static void toOne(int num, int cnt) {
		if(num==1) {
			ans = Math.min(ans, cnt);
			return;
		}
		
		if(cnt >= ans) return;
		
		if(num%3==0) {
			toOne(num/3, cnt+1);
		}
		if(num%2 ==0) {
			toOne(num/2, cnt+1);
		}
		toOne(num-1, cnt+1);
	}
}

 

풀이 코드  (Bottom-up)

바텀업 설계도 크게 다르지 않다.

1. i : 2~n으로 순차탐색을 하여 i를 만드는 경로의 수를 dp배열에 저장한다.
   1. i-1로 뺴준 연산 횟수에 +1  dp[i] = dp[i-1] +1;
   2.  i/2로 나눈 수의 연산값과 1번에서 구한 연산값 중 최솟값 if(i%2==0) 
   3.  i/3 로 나눈 수의 연산값과 1번에서 구한 연산값 중 최솟값 if(i%3==0) 

import java.io.*;

public class Main {
	
	public static void main(String[] args) throws  IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		System.out.println(bottomUp(n));
	}
	
	static int bottomUp(int num) {
		int[] dp = new int[num+1];
		
		for(int i=2; i<num+1; i++) {
			dp[i] = dp[i-1]+1; // -1 
			if(i%2==0) {
				dp[i] = Math.min(dp[i], dp[i/2]+1);
			}
			if(i%3==0) {
				dp[i] = Math.min(dp[i], dp[i/3]+1);
			}
		}
		return dp[num];
	}
}