[백준] 1322번. X와 K(JAVA)

문제

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

---

풀이(22분)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long x = Long.parseLong(st.nextToken());
        long k = Long.parseLong(st.nextToken());

        List<Long> availableBits = new ArrayList<>();
        long curNum = 1;

        while ((1L << availableBits.size()) <= k) {
            if ((x | curNum) != x) {
                availableBits.add(curNum);
            }
            curNum <<= 1;
        }

        long result = 0;
        for (int i = availableBits.size() - 1; i >= 0; i--) {
            if (k == 0) break;
            long power = 1L << i;
            if (k >= power) {
                result += availableBits.get(i);
                k -= power;
            }
        }

        System.out.println(result);
    }
}

---

문제 풀이 전략

 

풀이 자체만 이해하면 비트 연산을 이용한 코드 구현이 어려웠던 문제이다.

풀이는 간단하다.

OR연산을 한 값이 덧셈을 한 값과 동일하려면 X의 0의 자리에 0 또는 1만 채워넣는 것이 가능하다.

 

문제 예시인 5를 보자.

그렇다면 5 = 101이다.

첫번째 Y는 그렇기에 10인 2가 되는 것이다.

이런 식으로 X의 0의 자리를 채워가며 경우의 수를 따지다가 원하는 인덱스를 찾으면 거기서부터 맞춰주면 되는 것이다.