[백준 풀이_Java] 1463 1로 만들기

 

 

 

나의 처음 생각

 

3으로 나누었을 때 나머지가 0인지, 그리고 0이 아닐 때 홀수인지 짝수인지로 구분해서 어떤 규칙을 찾아내려고 했었다

그런데 규칙 찾기에는 실패했고 숫자를 키워가면서 경우의 수를 따졌을 때 더 작은 숫자들의 나누기가 반복되는 것을 느꼈다

예를들어, 숫자 22를 갖고 연산할 때 22-> 21-> 7-> 6-> 2-> 1 에서 7을 갖고 연산할 때의 경우가 똑같이 반복되었다

구글링을 한 결과 '동적 계획법(Dynamic Programming)' 을 사용한 풀이임을 알게되었다

 

 

 

 

 

Bottom-Up 방식

 

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

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());
		int[] dp = new int[N+1];
		
		dp[0]=0;
		dp[1]=0;
		
		for(int i=2; i<=N; i++) { // 2부터 N까지 반복문 = Bottom-Up방식
			dp[i] = dp[i-1]+1; // 기본 연산 횟수는 이전 연산 횟수+1 로 설정
			
            		// %3==0 이면 더 작은수로 설정
			if(i%3==0) dp[i]= Math.min(dp[i/3]+1, dp[i]); 
            		// %2==0 이면 더 작은수로 설정
			if(i%2==0) dp[i]= Math.min(dp[i/2]+1, dp[i]); 
		}
		System.out.println(dp[N]);
	}

}

 

 

 

다른 풀이

 

Top-Down 방식

 

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

public class Main {
	static int[] dp;
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		dp = new int[N+1];
        
		System.out.println(recur(N));
	}
    
	static int recur (int num) {
		if(num==1 | dp[num] >0) { // num이 1이거나, num의 연산 횟수가 이미 있다면
			return dp[num]; // 기존 dp[num] 리턴
		}
        
		dp[num] = recur(num-1)+1; // 기본 연산 횟수를 num-1 을 recur 한 수+1 로 설정
		if(num%3 ==0) { // %3==0일때
			dp[num]=Math.min(recur(num/3)+1, dp[num]);
		}
		
		if(num%2 ==0) { // %2==0일때
			dp[num]=Math.min(recur(num/2)+1, dp[num]);
		}
		
		return dp[num];
	}
}

 

그런데 Top-Down 방식은 재귀함수를 사용해서 백준에서 답변으로 제출 시 시간초과가 난다

재귀를 사용하는 방법도 있지만 이 경우에는 Bottom-Up 방식이 더 효율적이다