[ 백준 ] 12852 1로 만들기 2

Link | 12852번 문제 : 1로 만들기 2

Solution

DP로 해결하면 되는 문제이다.

X - 1부터 1까지 내림차순으로 탐색하며 점화식을 실행하면 된다.

현재 탐색하는 숫자가 x일 때 점화식은 다음과 같다.

x.count = MIN{(x * 3).count, (x * 2).count, (x + 1).count} + 1

다만, 3x 와 2x 는 NUM을 벗어나면 비교하지 않는다.

Example

문제 예시로 나온 X = 10을 생각해보자.

숫자들의 count를 저장하는 배열과 부모 숫자를 저장하는 배열을 생성한다.

부모를 저장하는 배열은 이후 연산 과정을 출력하기 위함이다.

X = 10;
int[] counts = new int[X + 1];
int[] parents = new int[X + 1];

배열을 표로 나타내면 다음과 같다. (빈칸은 0이다.)

• Search 9
  27, 18은 X를 벗어났기 때문에 고려하지 않는다.

• Search 8
  24, 16은 X를 벗어났기 때문에 고려하지 않는다.

• Search 7
  21, 14는 X를 벗어났기 때문에 고려하지 않는다.

• Search 6
  18, 12는 X를 벗어났기 때문에 고려하지 않는다.

• Search 5
  15는 X를 벗어났기 때문에 고려하지 않는다.
  10과 6중에서 10.count가 더 작기 때문에 10을 선택한다.

• Search 4
  12는 X를 벗어났기 때문에 고려하지 않는다.
  8과 5중에서 5.count가 더 작기 때문에 5를 선택한다.

• Search 3
  9, 6, 4중에서 9.count가 가장 작기 때문에 9를 선택한다.

• Search 2
  6, 4, 3중에서 3을 선택한다. (4.count와 3.count가 같지만 아무거나 선택해도 된다.)

• Search 1
  3, 2중에서 3.count가 더 작기 때문에 3을 선택한다.

위의 과정을 통해 X에서 1까지 변환하는 가장 적은 연산 횟수는 3회이다.

연산 과정은 parents 배열을 통해 확인할 수 있으며 10 -> 9 -> 3 -> 1 이다.

Code

Github Repository

private static int[] counts;
private static int[] parents;

private static void solution() throws IOException {
    final int NUM = Integer.parseInt(reader.readLine());
    counts = new int[NUM + 1];
    parents = new int[NUM + 1];

    for (int num = NUM - 1; num >= 1; num--) {
        if (num * 3 <= NUM) ignition(num, num * 3, num * 2, num + 1);
        else if (num * 2 <= NUM) ignition(num, num * 2, num + 1);
        else ignition(num, num + 1);
    }

    int num = 1;
    Stack<Integer> nums = new Stack<>();
    while (num != 0) {
        nums.push(num);
        num = parents[num];
    }
    result.append(counts[1]).append("\n");
    while (!nums.isEmpty()) result.append(nums.pop()).append(" ");
}

private static void ignition(int child, int... nums) {
    int minCount = Integer.MAX_VALUE;
    int parent = 0;
    for (int num : nums) {
        if (minCount > counts[num]) {
            minCount = counts[num];
            parent = num;
        }
    }
    parents[child] = parent;
    counts[child] = counts[parent] + 1;
}