Baekjoon #1463 1로 만들기

1로 만들기

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

문제

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

입력

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

 

출력

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

---

Dynamic Programming (동적 프로그래밍, 동적 계획법)을 이용하는 나의 첫 번째 문제이다.

아마 백준에서 DP를 이용하는 가장 쉬운 문제가 아닐까 싶다.

 

동적 프로그래밍이란, 어느 특정한 값을 구하기 위해서 순서 상 그 전의 값을 알아야하는 문제가 있을 때, 그 전의 값을 기억함으로써 계산량을 줄여서 푸는 방법이다.

다시 말해서, 어떤 값에 대해 그 값이 이전에 계산했던 값들이라면 그 값을 다시 계산하지 않고 이전에 계산했던 그 값을 가져와서 재활용한다. 여기서 새로운 값이 나왔을 때 그 값을 기억하기 위한 저장공간이 필요하다.

 

처음에는 dp 관련 문제가 처음이기도 하고, 배열 길이를 어떻게 해야할 지 생각을 못해서 (라기 보다는 안한게 틀림없다) Map을 이용하여 메모라이즈를 위한 공간을 이용하고 함수를 자주 호출하였다. 맞긴 맞았는데 아마 Map의 메모리 구조와 함수 호출 스택이 너무 많이 쌓여서 메모리가 상당히 높게 잡히고 시간도 다소 오래걸리는 것 같아 다시 작성하였다.

(기존 코드...)

/*
* 1로 만들기
* https://www.acmicpc.net/problem/1463
* */

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class P1463 {
    static Map<Integer, Integer> map = new HashMap<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        map.put(1, 0);
        map.put(2, 1);
        map.put(3, 1);

        int n = sc.nextInt();

        System.out.println(getRn(n));

        sc.close();
    }

    static int getRn(int n) {
        if (map.containsKey(n)) {
            return map.get((Object)n);
        }
        else {
            return 1 + min(n);
        }
    }

    static int min(int n) {
        int min = 1000001;
        int t = 0;
        if (n % 3 == 0) {
            t = getRn(n / 3);
            if (min > t) {
                min = t;
            }
        }

        if (n % 2 == 0) {
            t = getRn(n / 2);
            if (min > t) {
                min = t;
            }
        }

        t = getRn(n - 1);
        if (min > t) {
            min = t;
        }

        map.put(n, min + 1);

        return min;
    }
}

메모리 사용량이 너무 많다.

---

풀이

큰 문제를 작은 문제로 쪼개서 푸는 방법을 생각해내었다.

Rn을 n에 대한 연산 최소 횟수두고 Rn이 어떻게 계산 되어 나오는지 확인해보았다.

즉, n에 대해서 3가지 가능한 연산 방법 중 한가지를 한 이후에 결과값 m에 대해 Rm을 더한 값과 같다는 것을 알 수 있었다.

 

예를 들어, R10을 구하려고 한다면

10은 2번 식을 사용하면 5, 3번 식을 사용하면 9가 된다.

(+1 해주는 이유는 연산을 한번 했기 때문이다.)

 

R10 = 3 = min(1 + R5, 1 + R9)

 

R5 = min(1 + R4)

R9 = min(1 + R3, 1 + R8)

R8 = min(1 + R4, 1 + R7)

R7 = min(1 + R6)

...

 

따라서 아래와 같은 식이 성립한다.

최대 3개까지의 수를 비교해서 최솟값이 Rn 값이 된다.

 

Rn을 재귀 호출하면 될 것이다.

R 값에 대한 메모라이즈 배열을 하나 두고 만약 이값이 아직 계산되지 않은 값이였다면 계산을 실행하고 이미 계산되어 값이 저장되어 있다면 계산을 할 필요없이 그 값을 바로 return 해주면 될 것이다.

 

* Java에는 Math.min(int a, int b)가 있다. 이 함수를 활용하자.

(만약 3개를 한번에 비교하고 싶다면 다음과 같이 만들어도 된다.)

static int min(int... n) {
    int min = Integer.MAX_VALUE;
    for (int num : n) {
        if (min > num) {
            min = num;
        }
    }
    return min;
}

이것도 또 다른 함수 min을 호출하는 것이라 메모리가 많이 사용되는 것 같다.

 

n에 대해 1번 수식이 가능하면 n/3과 n-1을 비교하고

2번 수식이 가능하면 n/2와 n-1을,

1번, 2번 수식이 모두 가능하면 n/2, n/3, n-1을 비교,

1번 2번 모두 해당이 안된다면 단순히 n-1을 대입하면 된다.

 

코드 작성 전 간단하게 수도코드 비슷하게 나타내면

dp[] dp[0] = dp[1] = 0 getRn(n) {     if (dp[n] != null)         return dp[n]     else         dp[n] =          if n%6==0: min(getRn(n/2), getRn(n/3), getRn(n-1))         elif n%2==0: min(getRn(n/2), getRn(n-1))         elif n%3==0: min(getRn(n/3), getRn(n-1))         else: getRn(n-1)         return dp[n] }

---

전체 코드

/*
 * 1로 만들기
 * https://www.acmicpc.net/problem/1463
 * */

import java.util.Scanner;

public class Main {
    static int[] dp;

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

        int n = sc.nextInt();

        dp = new int[n + 1];
        dp[0] = dp[1] = 0;

        System.out.println(getRn(n));

        sc.close();
    }

    static int getRn(int n) {
        // check 0 and 1 (dp 배열이 0 값으로 초기화 되어 있기 때문에 n이 0 또는 1 일 때는 Rn을 다시 계산해서는 안된다.)
        if (n==0 || n==1) {
            return 0;
        }

        if (dp[n] == 0) {
            if (n % 6 == 0) {
                dp[n] = Math.min(Math.min(getRn(n / 2), getRn(n / 3)), getRn(n - 1)) + 1;
            } else if (n % 3 == 0) {
                dp[n] = Math.min(getRn(n / 3), getRn(n - 1)) + 1;
            } else if (n % 2 == 0) {
                dp[n] = Math.min(getRn(n / 2), getRn(n - 1)) + 1;
            } else {
                dp[n] = getRn(n - 1) + 1;
            }

        }
        return dp[n];
    }
}

 

cf. dp 배열을 Integer와 같이 객체로 선언하면 Rn에 대한 값이 없을 경우 null 값이기 때문에 n이 0과 1일 때 확인 할 필요 없이 if (dp[n] == null)만 이용해도 된다.