Diary/오일러프로젝트300번문제2 페이지의 소스 보기

내용출력
로그인[l]
수정할 수 없습니다: Diary/오일러프로젝트300번문제2 는 읽기 전용 페이지입니다.
#TEMPLATE [[Diary/DynamicTemplate]]
<div class="diary">
== [[/오일러프로젝트300번문제2]] ==

* [[/오일러프로젝트300번문제]]

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

[http://codepad.org/R11yupUG 제가 짠 코드]에서 256라인 쪽을 보면
{{{#!vim perl
        # 그런데 스트링의 뒷부분이 0으로 채워진 곳은 굳이 검사할 필요가 없다.
        # 예를 들어 001101110000000 패턴의 경우 마지막 PPPPPPP 는 어떻게 접히든 H-H의 갯수와 무관.
        # 따라서    00110111        패턴이라 생각하고 길이 8짜리 형태들과 비교하면 된다.

        my $t_length;       # 실제 검사할 길이 (마지막 "1"까지의 길이)
        if ( $str =~ /1(0*)$/ ) {
            $t_length = $length - length($1);
        }
}}}
라고 되어 있는데... 계산에 걸리는 시간을 줄이기 위해서 검사대상의 수를 줄이려는 방법 중의 하나였고, 실제로 꽤 시간절약을 할 수 있었습니다만...

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

<code>101010010</code> 를 접을 경우, 끝의 0을 빼고 생각한다면 다음과 같이 접힙니다.
{{{
 65         00
074        111
123        010
* H-H가 만나는 지점은 세 곳
}}}
그러나 실제로는 저렇게 접힐 수가 없죠;;; 7다음 8번 원소가 붙을 자리가 남지 않으니까... 실제로는 다음과 같이
{{{
 65         00
874        011
 03         10
 12         01
* H-H가 만나는 지점은 두 곳
}}}
최적으로 접혀도 두 곳밖에 생기지 않습니다.

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

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

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

===== Comments & Trackbacks =====

신난게 눈에 보여.. 새벽에 눈도 못뜬 상태에서 다 풀었다고 하면서, 의기양양했음. <mysign([[Zehn02]],2010-9-15 8:54 am)>
<longcomments(100)>

----
[[주인장분류]]
</div>
Diary/오일러프로젝트300번문제2 페이지로 돌아가기 | 다른 수정본 보기