백준 이진수 변환(17395)

이진수 변환

1. 힌트

1) $1$개 이상의 $1$을 $0$으로 바꾸는 변환을 정확히 $N$번 해야하므로 당연히 bitCount($x_0$)$< N$이라면 불가능합니다. 또한, $D(X)$의 최댓값은 아무리 줄여봤자 최상위 비트의 값이 됩니다. 따라서 최솟값을 최대화해야합니다.

2) bitCount($x_0$) $= N + 1$인 경우, 변환도중에 한 번에 $2$개의 비트를 변환하는 과정이 반드시 존재합니다. 이 때 켜져 있는 최하위 비트 $2$개를 변환하는 것이 최적해입니다.

3) bitCount($x_0$) $= N + K$인 경우에는 어떨까요? 켜져 있는 최하위 비트 $K + 1$개를 변환하는 것이 최적해입니다.

2. 접근

1) 극단적인 조건

$1 \le x_0 \le 10^{16}$은 $64$비트 정수 자료형 long보다는 작습니다. 따라서 $x_0$에 있을 수 있는 최대 켜져있는 비트는 $64$비트보다는 작다고 생각할 수 있습니다. bitCount($x_0$)의 값을 $cnt$라고 하겠습니다.

$cnt < N$인 경우는 어떨까요? 아무리 적어도 한 번에 한 개의 비트는 변환해야하니까 정확히 $N$번만에 $0$으로 변환하는 것은 불가능합니다. 반면에 $cnt \ge N$인 경우는 언제나 변환할 수 있음을 알 수 있습니다.

$D(X)$는 변환 과정에서 생기는 차들의 집합입니다. 최댓값 - 최솟값을 최소화하고자 한다면 당연히 최댓값은 작게, 최솟값은 크게 만들도록 노력해야겠죠.. 그런데 최댓값은 아무리 작게 만들어봐야 가장 큰 비트를 변환할 때 보다 작게 만들수는 없습니다. 최솟값을 크게 만드는 것이 관건입니다.

2) cnt = N일 때

$x_0$에서 아무 비트나 $1$개씩 줄여가면 $0$로 만들 수 있습니다. $D(X)$는 변환 과정에서 생기는 차들의 집합이기 때문에, 변환하는 순서는 상관이 없습니다. $D(X)$의 최대는 가장 큰 켜진 비트, 최소는 가장 작은 켜진 비트가 되겠죠.

3) cnt = N + 1일 때

변환은 $N$번 해야하는데 비트 수가 $1$개 더 많습니다. 중간에 한 번에 $2$개를 변환하는 과정이 있어야겠죠. $D(X)$의 최솟값을 최대화하기 위해서는 최하위 켜진 비트 $2$개를 켜는것이 최적입니다. 이걸 확장시켜서 일반화할 수 있습니다. $cnt = N + K$라면 $D(X)$의 최솟값을 최대화하기 위해서 최하위 켜진 비트 $K + 1$개를 동시에 꺼줍니다. 이제 남은 비트는 $N - 1$개가 남았고 남은 횟수도 $N - 1$개이므로 아무 비트나 한 개씩 끄면서 됩니다.

3. 구현

public class Main {

    static String solve(long B, int N) {
        int cnt = Long.bitCount(B);
        if (cnt < N) return "-1";
        StringBuilder bw = new StringBuilder();
        int range = cnt - N + 1;
        // 제일 처음에 끝에서 range개의 비트를 제거
        for (int i = 0; i < range; i++) B -= (B & -B);
        bw.append(B).append(" ");
        while (B > 0) {
            B -= (B & -B);
            bw.append(B).append(" ");
        }
        return bw.toString();
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder bw = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        long B = Long.parseLong(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        bw.append(solve(B, N)); 
        System.out.println(bw);
    }

}

1) 시간 복잡도

$O(log{10^{16}})$