[백준 18789] 814 - 2 (11008점)

티어: 루3

 

유전 알고리즘이 사실상 정해라는걸 이미 유명하게 알고 있었기 때문에 첫 방향성을 잡기는 쉬웠고, AC 기준인 8140점을 넘기기까지 고비는 6000점대에 있었는데, 순열화라는 기가막힌 아이디어를 찾아내서 결국 뚫어냈다.

 

이후에 10000점을 목표로 하고 상당히 고민을 많이했었다. 격자를 좀 더 직관적으로 보기 위해 격자 분석기도 html로 만들어보고, 격자에서 현재 없는 숫자가 어떤게 있는지 전부 표시하게도 해봤다. 그러다 알게 된 사실은, 실제로 1부터 10000까지 중에 격자가 만들 수 없는 숫자의 개수는 상당히 적다는 것이다. 가령 8997점을 맞았던 격자는 8998, 9789, 9889 단 3개를 제외한 모든 숫자가 있었는데, 이러한 격자는 조금만 손을 보면 충분히 1부터 10000까지 찾을 수 있을것 같았다. 그래서 방향을 조금 틀어서, 1부터 10000까지 중에 찾을 수 있는 숫자의 개수를 줄이는 방향으로 코드를 짜보기로 했다.

 

그 전에 이미 제출했던 격자들의 가능성을 시험해보기 위해 먼저 테스트를 해봤고, 놀랍게도 3000점 언저리밖에 받지 못한 격자가 9990개가 넘는 숫자를 찾을 수 있는 등 수많은 격자들에게 가능성이 보였다. 이 격자들을 순열화해서 점수를 높인 뒤 SA를 돌리게 되면, 격자의 태생이 9990개가 넘는 숫자를 가지고 있었기 때문에 몇개의 숫자가 없어지고 점수가 높아져도 여전히 많은 숫자를 가지고 있게 된다.

 

이러한 친구들을 모으고 골라 맥북을 혹사시켜서 결국 10010점짜리 격자를 찾아냈다.

 

그 이후에는 10000점이 넘는 다른 분들이 제출한 격자를 거름삼아 계속 점수를 올려나갔고, 맥북 CPU 온도가 한계에 다다를무렵에 11008이라는 최고치를 찍고 그만두었다.

 

몇가지 팁으로, 8140점을 목표로 하는것과 10000점 이상을 목표로 하는것은 그 방법과 과정이 다르다. 순열화의 원리 자체가 숫자 전체 쌍을 바꿔서, 없는 숫자들을 최대한 8000점 이상 뒤로 미뤄서 고득점을 노리는 반면에 10000점을 넘기 위해선 결국 1부터 9999까지 모두 찾을 수 있는 격자가 필요하기때문이다. 위에서 언급했듯이 10000점 이상을 목표로 하려면, 당장의 점수가 아니라 전체 격자에서 찾을 수 있는 숫자의 개수를 높이는 방향으로 생각해야한다.

 

실제로 11008점을 받기 위해서, 기존에 있던 8140점을 넘은 격자가 아닌 다른 격자를 사용했고, 지역해에 갇혀서 더이상 점수가 오르지 않을때에는 격자에서 찾을 수 있는 숫자의 개수를 최대한 높인 뒤, 그 격자를 다시 순열화를 통해 점수를 높이고 SA를 돌리는 과정을 계속 반복했다. 이렇게 되면 점진적으로 고득점을 받는 격자에 대해, 그 격자에서 찾을 수 있는 숫자의 개수가 증가하기 때문에 순열화를 통해 더 나은 점수를 받을 확률이 높아진다.

 

지애상수와는 다르게 계속 수작업으로 좋은 격자를 선별하고 여러 과정을 번갈아 거쳐야했기때문에 서버를 돌리는것보다 로컬에서 하는게 훨씬 간편했다. 자신의 컴퓨터 파워에 따라 달라질 수 있다.