1로 만들기

1. N = N - 1 로 만드는 방법 (비용 A)

2. N = N / K 로 만드는 방법 (비용 B , 나누어지는 경우에만 가능)

N을 1로 만들 수 있는 최소 비용을 찾는 문제이다.

 

while문의 첫번째 if문 조건이 핵심이라고 볼 수 있는데,

n을 k로 나눌 수 없는 경우 선택지가 a밖에 없으므로

n을 k로 나누었을 때의 나머지 * 비용 a < 비용 b 이면 1번 방법을, 아니면 2번 방법을 택하는 방식이다.

사실 여기까지만 해서 틀렸다.

즉, n%k==0인 경우를 조건에 넣어주지 않았기 때문에 n이 k로 나누어 지는 경우 0으로 판단되어 2번째 방법이 아예 실행되지 않았기 때문이다.

 

여기까지는 내가 작성한 코드인데 DP로 짜는 방법이 궁금해서 찾아보았다.

(사실 테스트에서 돌려보지 않아서 100% 맞는 코드는 아닐 수도..)

    public static long solution(int N, int K, int A, int B) {

        n = N;
        int k = K;
        int a = A;
        int b = B;

        while (n != 1) {
            System.out.println(n);

            if (((n % k) * a <= b) && (n%k!=0)) {
                n = calculateA(n, a);
            } else {
                int temp = n;
                n = calculateB(n, k, b);
                if (temp == n) {
                    n = calculateA(n, a);
                }
            }
        }

        return cost;
    }


    public static int calculateA(int n, int a) {
        System.out.println("calculateA");
        cost += a;
        return n - 1;
    }

    public static int calculateB(int n, int k, int b) {

        if (n % k == 0) {
            System.out.println("calculateB - 1");
            cost += b;
            return n / k;
        } else {
            System.out.println("calculateB - 3");
            return n;
        }
    }

---

yabmoons.tistory.com/501

(내가 푼 건 이 문제는 아닌데 비슷하다.)

 

포인트는 반대로 생각해서 점화식 만들기!

 

n을 1로 만든다 -> 1을 n으로 만든다

n=n-1 -> n=n+1

n이 k로 나누어지면 n=n/k -> n=n*k

 

DP[N] = DP[N-1] +1

DP[N] = DP[N/K] +1 (K가 3이라면 DP[6]은 DP[2]보다 비용이 1 크다)

 

결국, DP[N] = MIN(DP[N-1] +1,  DP[N/K] +1) 으로 계산하면 된다.

DP[0] = 0 , DP[1] = 0