이차원 평면에 다음 랜덤 숫자 생성기를 이용하여 좌표의 배열인 Pn을 생성하자:
S0=290797
Sn+1=Sn2 mod 50515093
Pn=(S2n,S2n+1)
P0,⋯,Pk-1 중 임의의 (서로 다른) 두 좌표의 최단 거리를 d(k)라고 하면, d(14)=546446.466846479이다.
소숫점 9자리까지 나오도록 반올림하여 d(2000000)을 구하시오.
--------------------------------------------------------------------------
번호가 높은 문제여서 해결한 사람이 많지 않지만, 5% 난이도 문제여서 그렇게까지 까다롭지는 않다.
초기값과 값을 구하는 공식, 해당 값을 이용한 좌표를 구하는 공식이 있으므로 요구하는 대로 값을 계산하면 된다.
다만, 예시를 보고 정확하게 프로그램을 작성하지 않아 한가지 실수가 있었는데, mod함수를 사용해서 연속된 두 좌표의 거리 중 가장 짧은 것을 계산한 것이었다. n개 좌표가 있으면 n-1번 계산했는데, 하필이면 예시가 12번째, 13번째 사이가 최단거리인 경우여서 잘못된 프로그램으로도 예시의 답이 나와서 잘못된 부분을 찾는데 애먹었다.
하지만, 곰곰히 생각해 보면, 문제에서는 임의의 두 좌표에 대한 거리를 묻고 있으므로 생성가능한 모든 조합에 대해 거리를 계산해야 되어서 시간이 매우 많이 필요하다. 복잡도가 O(n)에서 O(n2)이 되면서 시간이 기하급수로 늘어나는 문제가 있었다.
몇시간이 걸려도 해결되지 않아 코드를 일부 개선해봤지만 시간이 더 걸리는 등 알고리즘에 대한 근본적인 해결책이 필요했다. 관련 내용을 검색해보다 복잡도를 낮출 아이디어를 구했다. 2백만개의 좌표가 mod 함수에 의해 구해져서 들쑥날쑥이어서 모든 좌표 간의 거리를 계산했는데, 원점을 기준으로 정렬하면 앞뒤 좌표간의 거리만 계산해도 해결 가능하게 되어 복잡도가 줄어든다.
전체 실행시간을 보면, Pn 좌표를 생성하는데 3.6초, 원점 기준으로 정렬하는데 6초, 좌표 간 거리를 계산하는데 10초가 걸려 20초 만에 답을 구할 수 있었다.