[백준] 1463 1로 만들기 - DP(Dynamic Programming, 동적계획법) JAVA

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

코드설명

DP 문제입니다.

 

이 문제 같은경우 재귀로도 풀 수 있습니다만, DP로 해결했습니다.

 

Bottom-up 방식의 DP로 구현했고,

문제에서 핵심은 

1. dp[i] = dp[i-1] + 1 로직을 통하여 일단 dp[i]를 가장 N과 가까운값으로 먼저 처리합니다.

그래야만 무조건적으로 동작하는 코드로 비교값을 사용할 수 있습니다.

그 이후에, i%3 혹은 i%2 를 통하여서 최솟값을 갱신합니다.

이때, 처음에

if(i % 3 == 0 && dp[i/3] + 1< dp[i]) {
    dp[i] = dp[i/3] + 1;
}
else if(i % 2 == 0 && dp[i/2] + 1 < dp[i]) { //else가 없이 if로 처리해야됩니다.
    dp[i] = dp[i/2] + 1;
}

위의 코드처럼 else if로 처리하여 2일때가 오히려 최소로 갈 수도 있는 경우를 차단해버려서 오류가 났었습니다.

if 문으로 바꾸어서 해당 위치에서 갈 수 있는 최소값으로 갱신해야합니다.

 

 

코드

Bottom-Up

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

public class Main {
	public static int T, N;
	public static int answer = 0;
	public static int[] dp;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	
    	dp = new int[N+1];
    	
    	dp[0] = 0;
    	dp[1] = 0;
    	
    	for(int i=2; i<=N;i++) {
    		dp[i] = dp[i-1] + 1; //가장 N과 가까운 값으로 먼저 갱신
    		if(i % 3 == 0 && dp[i/3] + 1< dp[i]) {
    			dp[i] = dp[i/3] + 1;
    		}
    		if(i % 2 == 0 && dp[i/2] + 1 < dp[i]) {
    			dp[i] = dp[i/2] + 1;
    		}
    	}
    	
    	System.out.println(dp[N]);
    }
    
}

 

Top-DOWN 방식은 재귀방식때문인지 시간초과가 납니다.

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

public class Main {
	public static int T, N;
	public static int answer = 0;
	public static int[] dp;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	
    	dp = new int[N+1];
    	
    	System.out.println(simulate(N));
    }
    
    public static int simulate(int num) {
    	if( num == 1) { // 숫자가 1이 된경우에는 도착지점이므로 return 0해주어 종료시킵니다.
    		return 0;
    	}
    	if(dp[num] > 0) {
    		return dp[num];
    	}
    	dp[num] = simulate(num - 1) + 1;
    	if(num % 3 == 0) {
    		dp[num] = Math.min(dp[num], simulate(num/3) + 1);
    	}
    	if(num % 2 == 0) {
    		dp[num] = Math.min(dp[num],  simulate(num/2) + 1);
    	}
    	
    	return dp[num];
    }
    
}

 

Cache를 활용하여 시간초과 해결.

findOne(int x ) : 숫자 X를 1로 만들기 위해 필요한 최소 연산의 개수를 반환한다.

import java.util.*;
import java.io.*;

public class Main {
    public static int N, L;
    public static int[] arr;
    public static int[] cache;
    public static int answer = 0;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
        
		N = Integer.parseInt(st.nextToken());
		cache = new int[N+1];
		Arrays.fill(cache, -1);
		
		System.out.println(findOne(N));
	}
    
    public static int findOne(int X) {
    	if(X == 1) {
    		return 0;
    	}
    		
    	if(cache[X] != -1) return cache[X];
    	int ret = (int) Math.pow(10, 6);
    	//1. 3으로 나누는게 가장 효율적이다.
    	if(X%3 == 0) {
    		ret = Math.min(ret,findOne(X/3) + 1);
    	}
    	//2. 2로 나누는게 그 다음.
    	if(X%2 == 0) {
    		ret = Math.min(ret,  findOne(X/2) + 1);
    	}
    	
    	//3. 1을 뺴는게 그 다음.
    	if(X > 1)
    		ret = Math.min(ret,  findOne(X - 1) + 1);
    	
    	return cache[X] = ret;
    }
    
}