[28245] 배고파(Hard)

생각 유도

정말 많이 해맸다.
풀고 나서 보니 왜이렇게 어렵게 생각했을까 싶다.
최대 크기가 2^60 이므로 나이브하게 2^x + 2^y 에 해당하는 x와 y수를 구할 수 있다는 것만 알면 된다.
처음에 이분탐색으로 풀으려고 했는데, 2^x+ 2^y 를 정확하게 딱 떨어지지 않는 수를 구할 때 문제가 되었다.
그래서 2^x 에 해당하는 테이블을 만들어 놓고, 최대 차이가 작게 나는 수를 구한 뒤, 그에 해당 하는 비트 수를 출력하는 방식으로 했다.

방법

생각해야 할 것

• 수의 크기 : 10^18 이다. 이는 최대값으로 2^60 정도가 된다.

1. x 와 y의 수를 60 * 60 으로 구할 수 있다.
2. 2^x + 2^y 에 해당하는 작은 수 (=targetNum) 를 구한다.
3. targetNum 이 만약 1인 비트가 1개라면, 2의 거듭제곱으로 표현할 수 있으므로, 비트 자리 -1 를 두번 출력
   ex ) targetNum = 8 -> 2 2 로 출력해야함.
   그외 의 경우는 2의 거듭 제곱이 아니므로, 해당 비트를 출력
   ex) targetNum = 12 -> 2 3 로 출력.

알게 된 것

Long.bitCount : 해당 숫자에서 1인 비트가 몇개 있는지 알려주는 함수.

StringBuilder 를 쓰자. System.out.println 에 비해 몇배는 빨랐다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static StringTokenizer st = null;

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static int findIdx(long num) {
        int end = 64;
        int start = 0;
        int mid = -1;
        while (start < end) {
            mid = (start + end) / 2;
            if (num > (2 << mid)) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        return end;
    }

    public static long[] digit = new long[61];

    public static void main(String[] args) throws IOException {

        digit[0] = 1;
        digit[1] = 2;
        for (int i = 2; i <= 60; i++) {
            // digit 짝수 일 때,
            if (i % 2 == 0) {
                digit[i] = digit[i / 2] * digit[i / 2];
            } else {
                digit[i] = digit[i / 2] * digit[i / 2] * 2;
            }
        }
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            long num = Long.parseLong(br.readLine());
            long diff = Long.MAX_VALUE;
            long targetNum = 0;
            for (int t = 0; t <= 60; t++) {
                for (int tt = t; tt <= 60; tt++) {
                    if (diff > Math.abs(((1L << t) + (1L << tt)) - num)) {
                        diff = Math.abs(((1L << t) + (1L << tt)) - num);
                        targetNum = ((1L << t) + (1L << tt));
                    }
                }
            }
            if (Long.bitCount(targetNum) == 1) {
                for (int t = 0; t <= 60; t++) {
                    if ((targetNum & (1L << t)) > 0) {
                        sb.append(t-1).append(" ").append(t-1).append("\n");
                    }
                }
            }
            else {
                for (int t = 0; t <= 60; t++) {
                    if ((targetNum & (1L << t)) > 0) {
                        sb.append(t).append(" ");
                    }
                }
                sb.append("\n");
            }


        }
        System.out.println(sb);
    }
}

해당 문제

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