BaaaaaaaarkingDog
코딩, 해킹
[BOJ] 15896번: &+ +&

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

 

아주 오랫동안 헤매다가 풀이를 보고 해결했습니다. &+의 경우에는 각 자리를 따로 보면 되니까 쉬운데 +&를 어떻게 해야할지 좀 많이 어려웠습니다.

 

결론적으로 +&에서도 각 자리를 따로 보는데, 해당 자리가 1이기 위해서는 모든 +의 결과가 1이어야 한다는 것을 알 수 있습니다. 예를 들어 5번째 자리가 1인지 확인하려면 0xxxx + 0xxxx, 0xxxx + 1xxxx, 1xxxx + 0xxxx, 1xxxx + 1xxxx 의 결과에서 5번째 자리가 1인지를 보면 되는데 모든 xxxx를 다 볼 필요가 없이 가장 큰 것과 가장 작은 것만 보면 됨을 알 수 있습니다.

 

https://github.com/blisstoner/BOJ/blob/master/15896.cpp

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 15293번: Knapsack Cryptosystem  (0) 2019.10.21
[BOJ] 15896번: &+ +&  (0) 2019.10.15
[BOJ] 17513번: Hilbert's Hotel  (0) 2019.10.15
[BOJ] 10464번: XOR  (0) 2019.09.12
[BOJ] 16685번: XOR 포커  (0) 2019.09.12
[BOJ] 11191번: XOR Maximization  (0) 2019.09.12
[BOJ] 4798번: Dirichlet's Theorem  (0) 2019.09.11
  Comments
댓글 쓰기