[백준/파이썬] 12833번 XORXORXOR 풀이
업데이트:
문제 정보
- 문제 출처: 백준 온라인 저지
- 문제 링크: 12833번 XORXORXOR
- 문제풀이 코드 GitHub 링크
- 제출 언어: Python 3
풀이
문제
세 수 A, B, C를 입력 받은 다음, ( ( ( ( A XOR B ) XOR B ) XOR B ) … ) XOR B 형태로 연산을 C회 했을 때의 결과값을 출력하는 프로그램을 작성하시오.
코드
a,b,c=map(int, input().split())
for i in range(c%2):a^=b
print(a)
설명
이산수학 문제입니다.
XOR 연산이란, 두 피연산자의 bit가 다르면 1, 같으면 0입니다.
| X | Y | X xor Y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
파이썬에서의 xor은 ^ 기호를 연산자로 사용합니다.
B=0인 경우
0^0=1, 1^0=1로 bit가 계속 변하는 것을 알 수 있습니다.
B=1인 경우
0^1=1, 1^1=0으로 bit가 계속 변하는 것을 알 수 있습니다.
여기서 주목해야 할 것은, n번째 결과는 n+2번째 결과와 같다는 것입니다.
만약 109번의 연산을 직접 하게되면 제아무리 빠른 비트연산이라도 시간 초과가 날 것입니다.
따라서, 위에서 도출한 대로 연산 횟수가 몇번인지를 바탕으로 계산식을 압축하여 상수시간 내에 푸는 것이 정답입니다.
댓글남기기