[C++/DP] 백준 1463 1로 만들기

1. 문제

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

1463번: 1로 만들기

 

2. 풀이

입력 받은 수부터 연산을 수행해가며 가장 횟수가 적은 경우를 얻기 위해 DP 배열에 각 경우의 값을 저장한다.

입력 받는 수를 X라 했을 때, X/3, X/2 X-1로 총 3가지 연산이 가능하다.

1. 세 연산이 모두 가능한 상황 일 경우 X-1이 가장 큰 연산횟수가 드는 것이 확실히며
2. X-1 연산은 모든 경우에 가능하므로

X-1 연산을 한 경우의 값을 DP 배열에 가장 먼저 저장한다.

X-1 연산을 수행할 경우의 결과를 기본 값으로 두고 두 연산이 가능할 경우에 각각의 연산을 수행해 두 연산(X/3, X/2)으로 인한 결과가 X-1로 인한 결과보다 작을 경우 더 적은 횟수로 연산한 것이므로 이에 대한 값을 저장한다.

이 과정을 반복하면 DP[1]에 가장 작은 연산 횟수를 구할 수 있다.

 

3. 코드

import java.util.*;
import java.io.*;
 
public class Main {
    
    public static int dp(int n) {
        // n이 1일 경우 최소 연산 횟수를 먼저 저장
        int[] dp = new int[1000001];
        dp[0] = 0;
        dp[1] = 0;
 
        for (int k = 2; k <= n; k++) {
             // -1 연산은 항상 가능하고 가장 연산 횟수가 크므로 먼저 값을 저장
            dp[k] = dp[k - 1] + 1;
            if(k%3 == 0) // 3으로 나눴을 경우 연산 횟수가 더 적으므로
                dp[k] = dp[k] > dp[k / 3] + 1 ? dp[k/3]+1 : dp[k];
            if(k%2 == 0)
                dp[k] = dp[k] > dp[k / 2] + 1 ? dp[k / 2] + 1 : dp[k];
        }
        return dp[n];
    }
        
    public static void main (String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        System.out.println(dp(n));        
    }
}