[백준/JAVA] 1463번 1로 만들기 (dp)

문제

문제 링크

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

 

문제 설명

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

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

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다.

연산을 사용하는 횟수의 최솟값을 출력하시오.

 

힌트

10의 경우에 10 → 9 → 3 → 1 로 3번 만에 만들 수 있다.

 

제한 사항

• 1 ≤ N ≤ 10^6

 

입출력 예시

 

문제 풀이

접근 방법

• 3가지 연산을 적절히 사용해서 숫자 N 을 1로 만드는 최소 연산 횟수를 구해야한다.
• 처음에 헤맸었던게 마냥 2,3의 배수면 나눴던 것이 잘못된 방법이었다.
• -1, /2, /3 의 모든 경우의 수를 확인한 후 그중 최소로 연산하는 방식을 선택해야한다.
• 그러기 위해서는 모든 연산을 직접해야하는데 방법은 두가지가 있다.
  • top-down
    • N 에서 시작해서 -1, /2, /3 연산을 직접하는 것이다.
    • 모든 N 에서 N-1 은 -1 연산이 가능하고, 2,3 의 배수인 경우에는 /2, /3 연산이 가능하다.
    • 따라서 N 부터 1까지 하나씩 내려가면서 N-1, N/2, N/3 ... 최소로 되는 연산을 찾는거다
    • top-down 을 하기 위해서는 재귀함수를 사용한다.
  • bottom-up
    • 1 부터 시작해서 N까지 연산의 역순인 +1, *2, *3 연산을 한다.
    • 모든 수는 +1 이 가능하므로 이전 N-1 값에서 횟수 1을 더하고
    • 2, 3의 배수인 경우 N/2, N/3 의 연산 횟수에서 횟수 1을 더한 값과 비교해서 최솟값을 저장
    • 이런 계산을 반복해서 N까지 계산
• dp 문제는 접근 방식이 어려워서 여러 문제를 풀어보면서 감을 잡아봐야겠다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.List;

public class P_1463 implements Problem {

    // dp[i] 를 1로 만드는데 필요한 연산 횟수 카운트 배열
    private static int[] dp;

    @Override
    public void exec() throws Exception {

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

        int N = Integer.parseInt(br.readLine());

        br.close();

        // 정수 X에 사용할 수 있는 연산
        // 1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
        // 2. X가 2로 나누어 떨어지면, 2로 나눈다.
        // 3. 1을 뺀다.


        // dp 문제는 2가지 방법으로 푼다.
        // top-down, bottom-up
        // 3가지 연산을 수행하면서 가장 최소 연산 횟수로 1을 만들 수 있는지 찾기

        dp = new int[N+1];

        System.out.print(topDown(N, dp));

    }

    private static int topDown(int num, int[] dp) {

        // 1이면 연산횟수가 필요없다.
        if (num==1) {
            return 0;
        }

        // 3번 연산 (-1)
        // 이전 num-1 값에 +1 (3번연산) 수행횟수 더하기
        dp[num] = topDown(num-1, dp) + 1;


        // 1번 연산 (/3)
        // 숫자 num 의 최소 연산값 ( dp[num-1]+1 (3번연산) 과 dp[num/3]+1 (1번 연산) 중의 최솟값 )
        if (num%3==0) {
            dp[num] = Math.min(dp[num], topDown(num/3, dp)+1);
        }


        // 2번 연산 (/2)
        // 숫자 num 의 최소 연산값 ( dp[num-1]+1 (3번연산) 과 dp[num/3]+1 (1번 연산) (존재 시) 와 dp[num/2]+1 (2번 연산) 중의 최솟값 )
        if (num%2==0) {
            dp[num] = Math.min(dp[num], topDown(num/2, dp)+1);
        }

        return dp[num];
    }


    // 2. bottom-up (1 -> N)
    private static int bottomUp(int num, int[] dp) {
        for (int i=2; i<=num; i++) {
            // 3번 연산 (+1)
            // 숫자 1은 연산 횟수가 0, 2는 dp[1] + 1 -> -1 의 연산을 했기때문에
            // 이전 i 값에 +1 (3번연산) 수행횟수 더하기
            dp[i] = dp[i-1] + 1;

            // 2번 연산 (*2)
            // 숫자 i 의 최소 연산값 ( dp[i-1]+1 (3번연산) 과 dp[i/2]+1 (2번 연산) 중의 최솟값 )
            if (i%2==0) {
                dp[i] = Math.min(dp[i], dp[i/2]+1);
            }

            // 1번 연산 (*3)
            // 숫자 i 의 최소 연산값 ( dp[i-1]+1 (3번연산) 과 dp[i/2]+1 (2번 연산) (존재시) 와 dp[i/3]+1 (1번 연산) 중의 최솟값 )
            if (i%3==0) {
                dp[i] = Math.min(dp[i], dp[i/3]+1);
            }
        }

        return dp[num];
    }
    
    
    public static List<String> input = List.of(
            "2", "10"
    );
    public static List<String> output = List.of(
            "1", "3");

}