[백준]1463 1로 만들기

옛날에 비슷한 유형을 풀었었던 기억이 있어서 희미한 기억을 더듬어.. 거꾸로 접근을 했다.
2 x2
3 x3
4 x2 x2
5 x2 x2 +1
6 x3 x2
7 x3 x2 +1
8 x2 x2 x2
9 x3 x3
10 x3 x3 +1
11 x3 x3 +1 +1
12 x3 x2 x2
...
하지만 스스로 풀기 실패

package baekjoon;

import java.util.Scanner;

import static java.lang.Math.min;

public class Main_1463 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] dp = new int[N+1];

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

👩‍💻풀이..
반복문으로 풀었으니 bottom-up 방식으로 풀었다. (top-down 은 재귀호출 !!!)
Top-down 방식은 점화식을 이해하기 쉽다는 장점이 있고, Bottom-up 방식은 함수를 재귀 호출하지 않기 때문에 시간과 메모리 사용량을 줄일 수 있다는 장점이 있다고 한다.

풀이를 시작하자면..
나는 이해가 너무너무너무 잘 안돼서 손으로 직접 케이스별로 써서 이해했다 🥲 혹시 나처럼 이해 안되는 사람들에게 위로가 되기를 ..!! 한줄한줄 풀이 시작

dp는 기억하며 푸는 방식이다! 반복되는 연산을 기억해두고 메모리에 있는걸 갖다쓰기만 하면 된다. 그렇기 때문에 10을 1로 만드는 연산을 할 경우 1부터 10까지 필요한 최소 연산을 기억해두는 것이다.

[2]

dp[i] = dp[i-1]+1;

// dp[2] = dp[2-1]+1;
// dp[2] = dp[1]+1;
// dp[2] = 0+1;
// dp[2] = 1;

이 코드는 1씩 더해 연산했을 경우와 나누기를 실행했을 때의 경우 중 어느 것이 더 최소연산인지를 비교하기 위해 있는 코드이다. 1은 연산이 필요 없으므로 2부터 반복문이 실행되고 2에는 결국 1이란 값이 먼저 저장된다.

if(i%2 == 0) dp[i] = min(dp[i], dp[i / 2] + 1);

// dp[2] = min(dp[2], dp[2/2]+1);
// dp[2] = min(1, dp[1]+1);
// dp[2] = min(1, 0+1);
// dp[2] = 1;

그 다음 2로 나눠지기 때문에 이 조건에 걸려서 1에서 +1을 했을 때읭 연산이 최소인지, 2로 나눴을 때가 더 최소인지 비교하여 값을 담게된다. 최종적으로 dp[2]에 담기는 값은 1

[3]

같은 방식으로 3으로 넘어가면

dp[i] = dp[i-1]+1;
if(i%3 == 0) dp[i] = min(dp[i], dp[i / 3] + 1);

// dp[3] = dp[2]+1;
// dp[3] = min(dp[3], dp[1]+1);

3은 2에 1을 더한 연산이므로 먼저 직전 저장값에 1을 더해준다. 그 다음 해당 연산과 3으로 나누는 연산이 더 빠른지 비교한다. 맨 처음 1의 값에 1을 더해서 2로 만들고 또 1을 더해서 3으로 만들면 나오는 연산은 2 하지만 3으로 나눈다면 1. 최종적으로 dp[3] = 1

[4]

이해가 덜 될 수 있으므로 6까지만 해보겠다..! 2 3 4는 1을 더하나 나누나 최솟값이 같아서 .. 5는 +1뿐이 안되고..

dp[i] = dp[i-1]+1;
if(i%2 == 0) dp[i] = min(dp[i], dp[i / 2]+1);

// dp[4] = dp[3]+1;
// dp[4] = min(dp[4], dp[2]+1);

설명 생략! 3 만든 연산에 1을 더하면 2, 2 만든 연산에 2한번 더나누면 2

[5]

dp[i] = dp[i-1]+1;

// dp[5] = dp[4]+1;

5는 4만든 연산에 +1밖엔 방법이 없어서 5면 최소 세번 연산이 필요하다.

[6]

대망의 6!!

dp[i] = dp[i-1]+1;
if(i%2 == 0) dp[i] = min(dp[i], dp[i / 2]+1);
if(i%3 == 0) dp[i] = min(dp[i], dp[i / 3]+1);

// dp[6] = dp[5]+1;
// dp[6] = dp[6] = min(dp[6], dp[3]+1);
// dp[6] = dp[6] = min(dp[6], dp[2]+1);

5만든 연산에 단순히 1 더할지
3만든 연산에 2를 나눌지
2만든 연산에 3을 나눌지
선택하면 된다!
아 말로 하니까 너무너무 어려운데 중요 포인트는 최소 연산을 기억하는 것 !!!
6 이전에 이미 최소 연산 값이 있으니 거기서 어떤 걸 택해야 가장 최소가 되는지만 체크하면 된다.
dp[2]와 dp[3] 모두 필요 연산이 1이었기 때문에 dp[6]은 2가 된다. 2 or 3으로 만들어진 연산에 한번 더 나눠야되니 +1 해줘서 2 !
dp[5]+1은 당연히 탈락이다. 5를 만들기 위해 3번의 연산이 필요하고 거기에 1을 더해서 6을 만들면 총 4번의 연산이 필요하기 때문이다.
요렇게 -1 -1 /2 /2

스스로 풀진 못했지만 아무튼 이해는 야무지게 완료 .. 이제 적용해서 풀어보는 것이 중요할 듯 싶다 !!!! 너무 어려워서 주저리주저리 설명이 길었다 .. 화이팅 ..!!!!!!