어흥
[백준 1322] X와 K (Java) 본문
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/1322
1. 주의할 점
- 출력 결과를 Long 타입으로 출력한다
- 계산하는 과정에서 Int타입을 벗어날 수 있다
2. 구현
- X+A = X|A 를 만족하려면, X를 비트로 바꿨을 때, 0에 해당하는 부분을 1로 채워주면 된다
- 이 과정에서 위의 식이 성립하는 K번째로 작은 수를 구하기 위해 K도 비트로 바꾼다
- 왼쪽부터 시작해서 X의 0에 해당하는 부분이 현재 K를 비트로 바꿨을때 1이라면 해당하는 만큼의 수를 더하고 0이라면 더하지 않는다
(아래 TC 참조)
#1
X = 10 -> 1010
K = 5 -> 101
X = 1010
K = 1 0 1
Result = 2^0 + 2^4 = 17
#2
X = 11 -> 1011
k = 5 -> 101
X = 1011
K = 10 1
Result = 2^2 + 2^5 = 36
import java.util.*;
import java.lang.*;
import java.io.*;
class Main {
public static void main (String[] args) throws java.lang.Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
StringTokenizer st = new StringTokenizer(str);
int x = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
String sx = Integer.toBinaryString(x);
String sk = Integer.toBinaryString(k);
int klen = sk.length();
int xlen = sx.length();
int idx = klen-1;
long result=0;
char c;
for(int i=0;idx>=0;i++){
if(i<xlen) c = sx.charAt(xlen-1-i);
else c = '0';
if(c=='0'){
if(sk.charAt(idx)=='1'){
long vv = (long)Math.pow(2,i);
result+=vv;
}
idx--;
}
}
System.out.println(result);
}
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 17244] 아맞다우산 (Java) (0) | 2021.06.10 |
---|---|
[백준 1240] 노드사이의 거리 (Java) (0) | 2021.06.09 |
[백준 13701] 중복 제거 (C++, Java) (0) | 2021.06.09 |
[백준 18119] 단어 암기 (Java) (0) | 2021.06.08 |
[백준 3653] 영화 수집 (C++) (0) | 2021.06.02 |
Comments