[알고리즘/자바] 백준 1463번 - 1로 만들기

1463번: 1로 만들기

 

Dynamic Programming을 통해 풀어야하는 문제.

재귀를 통해 정답은 맞출수 있으나, 메모이제이션을 하지 않으면 시간초과가 발생한다. ( 중복된 연산을 제거해야한다 )

 

 

 

입력으로 10이 주어졌을때 수행방식을 작성해보면 다음과 같다. 여기서 f(n)은 n을 1로만드는 최소 연산횟수.

 

10이 들어왔을떄 3으로 나눌수 있는지 확인했는데 불가능하다. 그렇기 때문에 나누기2와 빼기1 연산만 수행했다. 

f(10) =  f(5)와 f(9)의 결과중 작은값 + 1

 

f(10) = min( f(5) , f(1) )  + 1 이므로 f(5) 와 f(1)을 구해야한다.

 

 

위의 개념을 코드화 하면 아래와 같다. 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedHashMap;

public class Main {
	
	
	static int[] dp = new int[1000001];
	
	
	public static void main(String[] args) throws IOException{
		
		
	
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.valueOf(br.readLine());
		
		dp[n] = toOne(n);
		bw.write(dp[n] + "\n");


		bw.flush();
		bw.close();
	}
	
	public static int toOne(int n) {
		
		if(n==1) {
			return 0;
		}
		else {
			
			ArrayList<Integer> temp = new ArrayList<>();
			if(n%3 == 0 ) {
				// n/3이 dp에 없으면 toOne 수행 (연산횟수 1회 추가)
				if(dp[(int)n/3] == 0 ) dp[(int)n/3] = toOne((int)n/3 ) +1;
				// dp[n/3]을 temp List에 add
				temp.add(dp[(int)n/3]);
			}
			if(n%2 == 0) {
				// n/2이 dp에 없으면 toOne 수행 (연산횟수 1회 추가)
				if(dp[(int)n/2] == 0 ) dp[(int)n/2] =  toOne((int)n/2) +1;
				// dp[n/2]를 temp List에 add
				temp.add(dp[(int)n/2]);
			}
			// n-1이 dp에 없으면 toOne 수행 (연산횟수 1회 추가)
			if(dp[n-1] == 0 ) dp[n-1] = toOne(n-1) +1;
			// dp[n-1]를 temp List에 add
			temp.add(dp[n-1]);
			
			//temp List에서 가장 작은 값을 구해서 반환
			int min = Collections.min(temp);
			return min;
		}
		
		
		
		
	
	}

		
}