[백준 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를 돌리는 과정을 계속 반복했다. 이렇게 되면 점진적으로 고득점을 받는 격자에 대해, 그 격자에서 찾을 수 있는 숫자의 개수가 증가하기 때문에 순열화를 통해 더 나은 점수를 받을 확률이 높아진다.

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