백준 1로 만들기

문제

 

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

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

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

입력

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

출력

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

예제 입력 1 복사

2

예제 출력 1 복사

1

예제 입력 2 복사

10

예제 출력 2 복사

3

힌트

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

---

해설

 

다이나믹 프로그래밍(동적 계획법)을 활용해 풀 수 있는 문제이다. 처음엔 어떻게 접근해야할 지 막막했었는데, N번째 수는 1로 만들 때까지 몇 번의 과정을 거치는 지를 가지는 배열을 만들어 저장하면, 문제를 풀 수 있다는 생각이 들었고, 이를 코드로 작성해 문제를 해결하였다.

 

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

public class Main {
    public static int[] numbers = new int[1000001];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Arrays.fill(numbers, -1);
        int N = Integer.parseInt(br.readLine());
        numbers[0] = 0;
        System.out.println(makeOne(N));
    }

    public static int makeOne(int N){
        // 기저 사례 : N번째 수가 -1이 아니면 해당 숫자를 리턴
        if(numbers[N] != -1)
            return numbers[N];
        // 기저 사례 : N이 1이면 리턴
        if(N == 1)
            return numbers[0];
        int divide3 = N;
        int divide2 = N;
        int min = N;

        int minus1 = 1 + makeOne(N - 1);
        if(N % 3 == 0) divide3 = 1 + makeOne(N / 3);
        if(N % 2 == 0) divide2 = 1 + makeOne(N / 2);


        min = Math.min(divide3, divide2);
        min = Math.min(min, minus1);
        numbers[N] = min;
        return min;
    }

}

 

하지만 이 코드는 백준에서는 답이라고 나오지만, 실제로 내 IDE에서 실행시켜보니 stack의 범위를 초과해 버리는 문제가 생긴다. 

그래서 다른 사람의 풀이를 보니 대부분이 BFS를 활용하거나 Bottom-Up 방식을 활용하였다.

 

다음은 Bottom-Up 방식의 풀이이다.

 

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

public class Main {
    public static int[] numbers = new int[1000001];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Arrays.fill(numbers, -1);
        int N = Integer.parseInt(br.readLine());
        numbers[1] = 0;
        numbers[0] = 0;
        for(int i = 2; i <= N; i++){
            numbers[i] = numbers[i - 1] + 1;
            if(i % 3 == 0 && numbers[i / 3] + 1 <= numbers[i]) numbers[i] = numbers[i / 3] + 1;
            if(i % 2 == 0 && numbers[i / 2] + 1 <= numbers[i]) numbers[i] = numbers[i / 2] + 1;

        }
        System.out.println(numbers[N]);
    }
}

 

어떠한가? 확실히 문제의 코드도 줄고, 시간도 줄었다. 시간이 줄어든 까닭은 재귀가 아니기 때문에, stack을 소모하지 않기 때문이다.

 

느낀 점

• 이 문제를 풀 때, 접근 방식(N번째 수가 1이 될 때까지 몇 번의 과정을 거치는 지를 저장)은 좋았지만, 꼭 재귀로 풀었어야 했는 지도 생각을 해봤어야 했다. 나의 경우엔 Top-Down 방식으로 풀었기 때문에, 재귀가 필수적이었지만, Bottom-Up 방식의 경우엔 단순히 배열의 값을 비교를 통해 해결할 수 있으니, 재귀가 필요하지 않게 된다. 
• 앞으로 동적 계획법 문제의 경우, Bottom-Up 방식도 고려해보도록 해야겠다. 물론 지금은 연습과정이기 때문에 Top-Down 방식의 풀이도 훌륭했다고 생각한다.