백준 1463 (1로만들기)

문제

---

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

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

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

 

 

 

 

 

 

풀이

---

간단하게 3으로 나누고 2로 나누고 둘다 안되면 1을 빼면 된다는 문제로 생각하면 큰코 다친다.

 

DP(Dynamic Programming) 문제의 예이다.

2가지 방식이 있다. Bottom-Up방식과, Top-Down 방식이 존재한다.

• Bottom-Up : 반복문을 통해 풀어내는 방식.
• Top-Down : 재귀를 통해 풀어내는 방식.

이 문제의 방식은 이렇다.

1부터 최솟값을 계속해서 저장을 한다.

6의 배수에서는 3로 나눴을때 값, 2로 나눴을때 값, 빼기 1로 계산했을때의 값의 크기를 비교해서 가장작은 값에 1을 더한다.

3의 배수에서는 3로 나눴을때 값, 빼기 1로 계산했을 때의 값의 크기를 비교해서 작은값에 1을 더한다.

2의 배수에서는 2로 나눴을때 값, 빼기 1로 계산했을 때의 값의 크기를 비교해서 작은값에 1을 더한다.

아무것도 아닌경우 빼기 1로 계산했을 때의 값에 1을 더한다.

 

이 네가지 경우를 나누어 재귀로 푸나 반복문을 푸나에 따라 방식이 달라진다.

 

우선 Top-Down 방식 코드다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {	
	
	static StringBuilder sb = new StringBuilder();
	static Integer[] dp;
	
	public static void main(String[] args) throws IOException{
		
	    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
	    
	    int n = Integer.parseInt(bufferedReader.readLine());
		
	    dp = new Integer[n + 1];
	    dp[0] = dp[1] = 0;	    
	    
		System.out.println(Count(n));
	}
	
	static int Count(int n) {
		
		if(dp[n] == null) {
		
			if(n % 6 == 0) 				
				dp[n] = Math.min(Count(n - 1), Math.min(Count(n /3), Count(n / 2))) + 1;
				
			else if(n % 3 == 0)
				dp[n] = Math.min(Count(n -1), Count(n/ 3)) + 1;
			
			else if(n % 2 == 0)
				dp[n] = Math.min(Count(n - 1), Count(n / 2)) + 1;
		
			else{
				dp[n] = Count(n - 1) + 1;
			}
		}
		
		return dp[n];		
	}
}

 

 

Bottom-Up 방식이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {	
	
	static StringBuilder sb = new StringBuilder();
	static Integer[] dp;
	
	public static void main(String[] args) throws IOException{
		
	    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
	    
	    int n = Integer.parseInt(bufferedReader.readLine());
		
	    int[] dp = new int[n+1];

	    for(int i = 2; i < n+1; i++){
	    	if(i % 3 == 0 && i % 2 == 0){
	    		int temp = Math.min(dp[i/3], dp[i/2]);
	            dp[i] = Math.min(temp, dp[i-1]) + 1;
	        }
	        else if(i % 3 == 0){
	            dp[i] = Math.min(dp[i/3], dp[i-1]) + 1;
	        }
	        else if(i % 2 == 0){
	            dp[i] = Math.min(dp[i/2], dp[i-1]) + 1;
	        }
	        else
	            dp[i] = dp[i-1] + 1;
	    }
	        System.out.println(dp[n]);
	}
}

 

 

해당 문제에서 자바로는 Bottom-Up 방식으로 풀었을 때 정답이 나왔다.

 

Top-Down 방식은 시간초과가 나왔다. 실제로 Top-Down 방식에서 1000을 넣게되면 StackOverflowError 가 발생한다. 메모리가 부족하다는 소리다. 

메모리와 시간을 적게쓰는 Top-Bottom 방식을 생각해봐야겠다.