Article Image
Article Image
read
문제
두 자연수 X와 K가 주어진다. 그러면, 다음 식을 만족하는 K번째로 작은 자연수 Y를 찾아야 한다.
| X + Y = X | Y |
| 는 비트 연산 OR이다. |
입력
첫째 줄에 X와 K가 주어진다. X와 K는 2,000,000,000보다 작거나 같은 자연수이다.
출력
| 첫째 줄에 X + Y = X | Y를 만족하는 K번째 작은 Y를 출력한다. 정답은 int 범위를 넘어갈 수 있다. |
예제 입력 1
5 1
예제 출력 1
2
풀이
이 문제는 수학적인 풀이가 필요한 문제였다.
| 우선 X+Y = X | Y 이려면 이진수로 나타냈을 때 X의 자릿수가 1이면 무조건 Y의 해당 자리수는 0이어야 한다. |
나머지 자리수는 K만큼 1을 더해주면 정답을 구할수 있다.
예제의 X=5를 예로들면 이진수로 바꾸면 X = 101 이다. 그러면 Y = ???…0?0 로 나타낼 수 있다.
K=1 00~0~1~0~
K=2 01~0~0~0~
K=3 01~0~1~0~ . .
0으로 고정된 부분을 제외하고 보면
K=1 001 -> 1
K=2 010 -> 2
K=3 011 -> 3
한마디로 X의 자리수중 1인 자리수는 0으로 고정하고 나머지 빈 부분에 K를 이진수로 표현한 자리수를 넣어주면 된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
long X = Long.parseLong(input[0]);
long K = Long.parseLong(input[1]);
System.out.println(sol(X, K));
}
static long sol(long X, long K) {
String strX = Long.toBinaryString(X);
String strK = Long.toBinaryString(K);
StringBuilder sb = new StringBuilder();
int idx = strK.length()-1;
for(int i=strX.length()-1; i>=0; i--) {
char c = strX.charAt(i);
if(c=='1') {
sb.insert(0, 0);
}
else {
if(idx==-1) continue; //K의 자리수를 모두 넣어줬을
sb.insert(0, strK.charAt(idx));
idx--;
}
}
while(idx>=0) { //K의 자리수 남았을 때
sb.insert(0, strK.charAt(idx));
idx--;
}
return Long.parseLong(sb.toString(), 2);
}
}