프로젝트 오일러 #152를 풀면서..

프로젝트 오일러 #152를 풀면서 몇가지 새롭게 구현했던 것들이 많았네요.

 

기본적으로 모든 조합을 찾기 위해서는 $O(2^n)$인 탓에, 35, 45개일 때는 그나마 적정한 시간에 구할 수 있었지만, 80개에서는 그것이 안 되었네요.

 

이럴 때, 경우의 수를 줄여주는 것이 필요한데, 어떤 식으로 경우의 수를 줄일 것인지 고민을 많이 했네요.  더더구나 문제가 3의 배수는 총 26개나 나온다는 것이었죠.

 

처음에는 그룹을 지어서 할 생각이었는데.. 그룹을 지으면 전혀 안 되는 문제라는 사실을 조금 고민하면서 알게 되었네요.   회사에 있으면서도 어떻게 풀까 고민했었는데..  결국 경우의 수를 줄이는 방법을 생각했고, 제 구닥다리 노트북에서도 0.1초에 답을 내었네요.

 

여러가지 연산시간을 줄이는 방법도 생각을 했었는데.. 예를 들어서 x란 숫자가 2의 n승인지 아닌지를 판단하는 방법..

 

일반적으로는

bool is2pow = false;
for( int i = 0 ; i < 31 ; i++ )
  if( x == (1<<i) ) { is2pow = true; break; }

형태로 짜야할텐데, 이렇게 하면, 평균적인 시간이 많이 들겠더라고요.

 

그래서 고민했던 것이..

bool is2pow = ((x&-x) == x);

였네요. 

 

그리고 실제 제가 필요한 것은 2의 홀수승이었는데..

2의 n제곱인 것만으로는 알 수 없으므로... 비트 검사를 또 했네요.

 

x & 0x5555555...55

 

사실 계산하려면.. ((unsigned)-1)/3 으로 위의 0x5555...55 숫자를 얻을 수 있겠죠.

 

여하튼 #152 풀기 위해서 고민 많이 했었는데, 몇가지 실수를 해서 헤매긴 했지만 재밌게 풀었네요.