1463.1로만들기

문제

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

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

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

## 입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

## 출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

풀이

알고리즘 흐름

이 문제는 재귀를 통해 문제를 풀이해야한다. 문제를 풀기위해 3가지 경우를 볼수있다.

• 3으로 나누는 경우
• 2로 나누는 경우
• 1을 빼는 경우
• • 6으로 나눠지는 경우

즉, 6으로 나눠지는 경우는 3으로 나누는 경우와 2로 나누는 경우, 1을 빼는 경우 모두 재귀호출 하여 3가지 경우 중 최솟값으로 DP를 갱신

3으로만 나눠지는 경우는 3으로 나누는 경우와 1을 빼는 경우를 재귀호출

2로만 나눠지는 경우는 2로 나누는 경우와 1을 빼는 경우의 수를 재귀호출

그 외에는 1을 빼는 경우만 재귀호출을 해주면 된다.

그리고 각부분에 이전 재귀 호출 중 최솟값에 1을 더한 값이 현재 N에 대한 최소 연산횟수가 된다.

이를 dp 배열에 메모이제이션 하면서 값을 구해 나간다.

코드

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

public class _1로만들기 {  

    static Integer[] dp;  

    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  

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

        dp = new Integer[n+1];  

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

        System.out.println(recursion(n));  
        br.close();  

    }  

    static int recursion(int n){  

        if(dp[n] == null){  
          //6으로 나눠지는 경우  
            if(n % 6 == 0){  
                dp[n] = Math.min(recursion(n-1), Math.min(recursion(n/3), recursion(n/2)))+1;  
            } 
            //3으로 나눠지는 경우
            else if (n % 3 == 0) {  
                dp[n] = Math.min(recursion(n/3), recursion(n-1))+1;  
            } 
            //2로 나눠지는 경우
            else if (n % 2 == 0) {  
                dp[n] = Math.min(recursion(n/2), recursion(n-1))+1;  
            }
            //안나눠지는 경우
            else {  
                dp[n] = recursion(n-1)+1;  
            }  
        }  

        return dp[n];  
    }  
}

다른방법

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int N = in.nextInt();
        System.out.println(recur(N, 0));
    }

    static int recur(int N, int count) {
        // N이 2 미만인 경우 누적된 count값을 반환
        if (N < 2) {
            return count;
        }
        return Math.min(recur(N / 2, count + 1 + (N % 2)), recur(N / 3, count + 1 + (N % 3)));

    }
}

메모이제이션을 사용하면 n-1의 값도 재귀호출하지만, 나머지값을 이용하여 count를 갱신하면 효율이 좀더 좋다.