ACM - 뱀

[2018-06-12]

링크: https://www.acmicpc.net/problem/10875

뱀의 모든 좌표를 한개씩 저장하게되면 약 40PB가 필요하다. 메모리 제한에 걸린다. 좌표를 하나씩 보는 것이 아닌 직선 정보처럼 양끝점을 가지고 있고, 뱀이 이동하면서 그러한 직선들이 계속 갱신되거나 합쳐진다면 뱀의 좌표들을 저장할 공간을 상당히 많이 줄일 수 있을것이다. 어차피 뱀은 수평방향과 수직방향으로만 이동하기 때문에, 방향성을 고려하지 않고 수평방향과 수직방향에 대한 정보를 map으로 저장했다. 최대 L*2(200MB)크기 만큼의 메모리가 필요하기에 주어진 조건에 맞다.

※ 더 최적화 할 수 있는 방법
직선이 아닌 사각형 형태로 저장할 수 있다면, 메모리를 더 줄일 수 있을거 같다. 문제는 사각형을 어떠한 기준으로 나눌 것인가 이다. 추후에 이 방법으로 풀어보려고 한다.