[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