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

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

1463번: 1로 만들기

접근 방법

단순하게 접근하면 3으로 나누고, 2로 나누고, 나눌 수 없으면 -1을 하면서 값을 작게 만들면 되지 않나 생각할 수 있다.

단순 접근 : 10 -> 5 -> 4-> 2-> 1 : 4번

정답 : 10 -> 9 -> 3-> 1 : 3번

쉽게 단순 접근은 틀린 걸 알 수 있다.

 

이유는 10을 1로 만드는 경우에 2가지 경우의 수가 생기게 된다.

1. 9를 1로 만드는 최솟값 + 1

2. 5를 1로 만드는 최솟값 + 1

두 값 중 더 작은 값이 최솟값이 된다.

 

그럼 문제에서 나온 3가지 경우를 보면

최솟값 = 입력값 -> 1로 가는 최소 횟수

1. 입력값이 3으로 나누어 떨어지는 경우, 3으로 나눈 값의 최솟값 + 1
2. 입력값이 2로 나누어 떨어지는 경우, 2로 나눈 값의 최솟값 + 1
3. 입력값의 직전 값 + 1

 

3가지로 보일 수 있지만 실제 문제에서 비교하는 값은 2가지 값만 비교하면 된다.

-> 나누어 떨어지는 경우 vs 나누어 떨어지지 않는 경우를 비교해 더 작은 최솟값을 택하면 된다.

 

Bottom Up

ex) 입력값이 3으로 나누어 떨어지는 경우, 3으로 나눈 값의 최솟값 + 1에서 3으로 나눈 값의 최솟값이 미리 계산되어있어야 한다.

그래서 바텀업 방식으로 계산해 나간다.

memoiration

dp[] 배열을 생성해 바텀업 방식으로 계산된 값을 저장해 둔다.

dp의 인덱스 값 = 입력값

초깃값은 dp[0], dp[1] = 0이다.

코드

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int input = Integer.parseInt(bf.readLine());

        /*
        input -> 1 까지 연산의 최솟값

        3가지 연산 가능
        input 이 3으로 나누어 떨어지면, 3으로 나눈다.
        input 이 2로 나누어 떨어지면, 2로 나눈다.
        아니면 1을 뺀다.

        그럼 조건식이 2개 나온다.
        input 이 2로 나누어 떨어지면, 2로 나눈 값 vs 1을 뺀 값
        input 이 3로 나누어 떨어지면, 3로 나눈 값 vs 1을 뺀 값

        초깃값
        dp[0] = dp[1] = 0
        */

        int[] dp = new int[input + 1];

        dp[0] = dp[1] = 0;

        // 2부터 하는 이유는 bottom up, 1은 이미 초기화되어있음
        for (int i = 2; i <= input; i++) {
            // 1을 빼는 경우 바로 직전의 위치 누적 값 + 1
            dp[i] = dp[i - 1] + 1;

            // 2로 나누어지는 경우 현재 누적 횟수 vs 2로 나눈 값의 누적 횟수 비교
            if (i % 2 == 0) {
                // 2로 나누어 떨어지는 경우 = i / 2위치 누적 값 + 1
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            }
            if (i % 3 == 0) {
                // 3로 나누어 떨어지는 경우 = i / 3위치 누적 값 + 1
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
            }
        }
        System.out.println(dp[input]);
    }
}