자바(백준) 1463 1로 만들기

이 문제는 dp의 가장 기본적인 문제라고 한다. 처음에 이 문제를 보았을 때에는 cnt 변수를 선언해서 연산을 할 때마다 더해준다라는 생각으로 접근을 했다. 하지만 cnt값을 계속 증가해주기 때문에 연산의 최소가 비교가 되질 않았다. 그래서 풀지 못하고 힌트를 보았다. 

 

그래서 보니 cnt을 설정하지 않고 -1 연산할 때,  /2 연산할 때, /3 연산할 때 +1을 해주는 것이다. 왜냐하면 연산을 해주었기 때문이다. 그래서 dp[n] 에는 n이 1이 될때까지의 연산 횟수를 저장하는 것이다. 

 

예로 10을 들어보자. 그러면 10을 1 뺄수 있고, 2로 나눌 수도 있다. 그러면 9 와 5가 된다. 여기서 9를 3 으로 나누고 또 3으로 나눌 수 있다. 총 연산 수는 3이다. 5를 -1 하고 4를 2로 2번 나누면 총 연산 수는 4이다. 그래서 연산을 할 때마다 +1을 시켜 각 연산마다 횟수를 비교시켜 최솟값을 구하면 되는 것이다. 

 

이 문제에 대해선 두 가지 방법이 있다. Bottom up 방식과 Top down 방식이다. Bottom up 방식은 i를 2부터 설정해서 N까지 아래에서부터 차례대로 올라간다. 그니까 dp[2] 부터 연산횟수를 저장해서 dp[N] 까지 구하는 것이다.

Top down 방식은 재귀함수를 이용해서 dp(N)을 구하기 위해서는 dp (N-1) dp(N-2) ... dp(1) 까지 구하는 방식이다. 

 

 

Top down 방식

import java.io.IOException;
import java.io.BufferedReader;    
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main { 
    
    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());
        
        int N = Integer.parseInt(st.nextToken());
        dp = new int[N+1];
        
        Arrays.fill(dp, -1);
        
        System.out.print(makeOne(N));
    }
    
    public static int makeOne(int n) {
        if(n == 1) return 0;
        if(dp[n] != -1) return dp[n];
        
        int result = makeOne(n-1)+1;
        if(n % 2 == 0) result = Math.min(result, makeOne(n/2) + 1);
        if(n % 3 == 0) result = Math.min(result, makeOne(n/3) + 1);
        dp[n] = result;
        return result;
    }
}
 

Bottom up 방식

import java.io.IOException;
import java.io.BufferedReader;    
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main { 
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int N = Integer.parseInt(st.nextToken());
        int[] dp = new int[1000001];
        
        dp[1] = 0;
        
        for(int i = 2; i <= N; i++) {
            dp[i] = dp[i-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);
        }
        
        System.out.print(dp[N]);
    }
    
}