/오일러프로젝트300번문제2

• /오일러프로젝트300번문제

뭐가 문제였는지 깨달았습니다.

[제가 짠 코드]에서 256라인 쪽을 보면

        # 그런데 스트링의 뒷부분이 0으로 채워진 곳은 굳이 검사할 필요가 없다.
        # 예를 들어 001101110000000 패턴의 경우 마지막 PPPPPPP 는 어떻게 접히든 H-H의 갯수와 무관.
        # 따라서    00110111        패턴이라 생각하고 길이 8짜리 형태들과 비교하면 된다.

        my $t_length;       # 실제 검사할 길이 (마지막 "1"까지의 길이)
        if ( $str =~ /1(0*)$/ ) {
            $t_length = $length - length($1);
        }

라고 되어 있는데... 계산에 걸리는 시간을 줄이기 위해서 검사대상의 수를 줄이려는 방법 중의 하나였고, 실제로 꽤 시간절약을 할 수 있었습니다만...

이게 샘플로 주어진 길이 8까지는 적용할 수 있는데 길이가 9 이상이 되는 순간 함정이 나오더군요.

101010010 를 접을 경우, 끝의 0을 빼고 생각한다면 다음과 같이 접힙니다.

 65         00
074        111
123        010
* H-H가 만나는 지점은 세 곳

그러나 실제로는 저렇게 접힐 수가 없죠;;; 7다음 8번 원소가 붙을 자리가 남지 않으니까... 실제로는 다음과 같이

 65         00
874        011
 03         10
 12         01
* H-H가 만나는 지점은 두 곳

최적으로 접혀도 두 곳밖에 생기지 않습니다.

트위터에서 [aer0님]이 자기가 푼 것과 제가 푼 결과가 길이9에서부터 달라지며, 자신이 푼 값이 더 작더라..는 정보를 주셔서... 길이9에서 패턴을 일일이 찍다보니까 눈에 들어왔습니다.

지금 생각하면 '왜 저런 착각을 했을까' 싶을 정도로 간단한 이유인데...;; 위와 같이 그 뒤에 원소가 추가로 붙을 자리가 남지 않는 경우가 길이9에서 처음 나타나고, 저는 계속 손으로 검증할 수 있는 길이 6정도에서만 그려보다보니까 눈치를 못 채고 있었네요. (샘플로 길이8의 값을 준 이유가 이걸 노린 것 같기도...?)

한시간 전에 이 오류를 깨닫는 순간 벌떡 일어나며 컵에 남은 음료수를 들이키다가, 태어나서 가장 심하게 사레가 들렸습니다. 익사할 때 심정을 조금은 느꼈는지도 -_-;;; 지금도 가슴이 얼얼하군요...

Comments & Trackbacks

신난게 눈에 보여.. 새벽에 눈도 못뜬 상태에서 다 풀었다고 하면서, 의기양양했음.

이름:  

Homepage:

내용:
 

---

주인장분류