[백준 12931번] 두 배 더하기

문제 링크: 12931번 두 배 더하기

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

 

전형적인 DP 문제라고 생각했는데 그리디한 접근이 필요한 문제였다. 내가 헷갈렸던 것은... 어떤 양의 정수를 0으로 만들고자 할 때, 2로 나누는 편이 1을 빼는 편보다 무조건 더 빠른가에 대한 대답이었는데, 이에 대한 답은 '그렇다'이다. 헷갈릴 일이 없는 건데... 아마도 1을 더하는 연산도 있는 경우를 두고 이상한 데서 고민한 것 같다. 참고로 1을 더하는 연산이 있다면, 15 → 16 → 8 → 4 → 2 → 1 → 0이 15 → 14 → 7 → 6 → 3 → 2 → 1 → 0보다 빠르다.

먼저, 양의 정수들에 대해서, 0으로 만들기 위한 횟수를 미리 구해두어야 하는데, 단순히 횟수가 아니라 0으로 만드는 과정에서 필요한 '1 감소 연산'과 '1/2배 연산'의 횟수를 각각 구해둔다. 각 수를 2진수로 고려했을 때 0, 1의 개수 등을 고려하여 그 횟수를 구해내는 스터디원 생각이 신박했는데... 일단 여기서는 평범하게 구하도록 한다.

어떤 과정으로든 해당 결과값은 다음과 같이 나올 것이다.

 

N	1 감소 연산	1/2배 연산
1	1	0
2	1	1
3	2	0
4	1	2
5	2	2
6	2	1
7	3	1
…	…	…

 

그리고 배열에서 '1 감소 연산'은 각 원소에 대해 각각 시행되어야 하므로 각 원소가 필요로 하는 횟수의 합을 더해주며, '1/2배 연산'은 모든 원소에 대해 동시에 시행되므로 각 원소가 필요로 하는 횟수 중 최댓값만큼만 시행하면 된다.

동시에 1/2배를 해야하니 더 걸릴 수도 있겠다고 생각되지만, [3, 5, 7]의 상태에서는 [2, 4, 6]으로, 2로 나눌 수 있도록 1개씩 빼야하는 예시를 생각해보면, 어차피 이 횟수는 모두 '1 감소 연산'에서 합을 구했기 때문에 포함되어 있다.

 

import java.io.*;
import java.util.*;

public class Main {
    static int n;

    public static void main(String[] args) throws IOException {
        int[][] dp = new int[1001][2];
        // dp[i][x]: num of operations required to make 0 from i
        // x = 0 for '-1', x = 1 for '1/2'

        dp[1][0] = 1; dp[1][1] = 0;
        for (int i = 2; i <= 1000; i++) {
            if (i % 2 != 0) {
                dp[i][0] = dp[i - 1][0] + 1;
                dp[i][1] = dp[i - 1][1];
            } else {
                dp[i][0] = dp[i / 2][0];
                dp[i][1] = dp[i / 2][1] + 1;
            }
        }

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int sum = 0;
        int max = 0;
        int t;
        for (int i = 0; i < n; i++) {
            t = Integer.parseInt(st.nextToken());
            sum += dp[t][0];
            if (dp[t][1] > max) max = dp[t][1];
        }

        System.out.println(sum + max);
    }
}