백준_1463번_1로 만들기_자바

백준_1463번_1로 만들기_자바

 

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

1463번: 1로 만들기

 

해당 문제는 다이나믹 프로그래밍이라고 불리는 DP문제입니다.

 

문제 해석 -

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

위의 3가지를 입력받은 수를 1로 만들때까지 반복하고, 가장 횟수가 낮은 경우의 수를 출력하면 되는 문제입니다.

 

주의사항 -

입력되는 N의 범위가 10의 6승까지 가능하므로, 메모제이션을 사용하지않으면 시간초과가 발생합니다.

 

- 메모제이션이란 ?

미리 계산한 값을 특정 배열에 저장하여, 중복계산을 하지 않도록 하는 방법입니다.

 

로직 -

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

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];
        dp[0] = 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.println(dp[n]);

    }
    
}