[백준 #1463] 1로 만들기

백준 #1463 1로 만들기

백준 #1463

---

문제 설명👩‍🏫

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

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.
   정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력해라.

입출력 예

입력
2

출력
1

---

내 코드💻

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int number = Integer.parseInt(br.readLine());

        int []arr = new int[number+1];
        arr[1] = 0;
        for(int i=2;i<=number;i++){
            arr[i] = arr[i-1] + 1;
            if(i % 2 == 0){
                arr[i] = Math.min(arr[i/2] + 1, arr[i]);
            }
            if(i % 3 == 0){
                arr[i] = Math.min(arr[i/3] + 1, arr[i]);
            }
        }
        System.out.println(arr[number]);
    }
}

---

설명💡

DP를 사용해서, 이미 계산한 값은 배열에 넣어두는 방식을 사용했다.
우선 입력된 값+1 크기 만큼의 배열을 정의해준다.
(0은 사용하지 않을 것이므로)

---

처음에는 자신의 값에서 -1 한 값으로 초기화를 시켜준다. 그 다음으로 2로 나눈 값의 위치 + 1 값이나, 현재 값 중에 작은 값으로 입력한다. 그 다음은 3으로 나눈 값을 비교하면 된다.
→ 이 부분이 가장 헷갈리는 부분이었다.🤔🤔

---

처음에는 3으로 나누거나, 2로 나눠지면 그 수로 나누고, 안되면 -1을 한 후에 또 계산하면 되겠지라는 안일한 생각으로 시작했다.
3과 2로 둘다 나눠지는 경우에도 3으로 먼저 나누면 같거나, 더 작은 값이 나오는 줄 알고 3으로 나누고, 2로 나누고, 1로 빼는 순서로 만들었다.
이 부분 때문에 틀렸다.....

---

3과 2로 둘다 나눠지는 경우 중에 작은 값은 3으로 나누면 같거나 더 작은 값이 나오지만, 14088의 경우에는 2를 먼저나누면 14번, 3을 먼저 나누면 15번이 나오게 된다...

---

그래서 -1로 먼저 초기화를 시킨 후에, 그 다음에 2 또는 3으로 나누면 된다...
하지만.. 여기서 또오 실수한 점은

// arr[i] = Math.min(arr[i/3] + 1, arr[i-1] + 1);
arr[i] = Math.min(arr[i/3] + 1, arr[i]);

위 아래가 같은 결과인 줄 알았다.. 초기화 직후에는 같은 값이지만, 첫번 째 비교후에는 달라질 수 있다.
즉, 위는 현재값과 비교하는게 아니고, 기존값과 비교하는 꼴이 되어버려서 틀린 답이 나온다..

---

실패한 코드(1차 시도)😟

import java.io.*;

public class Main {
    static int[] arr = new int[1000001];
    public static int func(int num){
        if(arr[num]!=0) return arr[num];
        
        else if(num == 1) return 0;
        else if(num == 2 || num == 3) return 1;
        else {
            if (num % 3 == 0) {
                return Math.min(func(num / 3) + 1, func(num - 1) + 1);
            } else if (num % 2 == 0) {
                return Math.min(func(num / 2) + 1, func(num - 1) + 1);
            } else {
                return func(num - 1) + 1;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int number = Integer.parseInt(br.readLine());
        System.out.println(func(number));
    }
}

시간초과....

---

실수한 부분😟

이전에 풀었던 피보나치를 생각하고 Top-down 방식으로 문제를 풀었는데, 이렇게 푸니까 시간초과가 떴다...
→ Bottom-up으로 다시 풀자!

---

느낀 점 및 궁금한 점🍀

Top-down이 안되서 Bottom-up으로 했는데.... 여기서 순서도 반대로 해야했고,, 안에 수식도 조금 달랐다.. 아주 그냥 정신없는 문제였다..

Top-down이 Bottom-up보다 더 많은 시간이 소요된다는 것을 알 수 있었다...😂