kisrin4319   7년 전

구현해야 하는 크기가 10^8 *10^8 정도 된다면 자바 같은 경우 어떤식으로 구현 해야할까요?

10875번 뱀 문제를 푸는데 크기 부터 어떻게 접근해야 될지 모르겠습니다 ㅠ

chogahui05   7년 전

문제가 만만치 않군요. 풀어보지는 않았고요..

그냥 문제를 읽어보고 난 느낌만 말씀드릴게요.


일단 회전 횟수가 꽤 작습니다. 크다면 더 어려워졌겠지만.. 작습니다. 1000이잖아요. O(n^2)로도 해결 가능하다는 소리지요.

그러면 이렇게 생각하실 수 있습니다.


i번째 회전 전에, 뱀이 간 궤적들과 만나는지 check한다.

선분과 선분이 교차하는지 검사하는 알고리즘은

O(1)로 해결이 가능하고요. (교점이 있는 경우에는 교점도 구해야겠죠. 교점이 무한개인 경우는, 최초로 만나는 점을 구하시면 되고요.)


따라서, i번째 회전 전에 뱀이 간 궤적들과 만나는지 check하는 알고리즘의 시간 복잡도는

O(i)가 됩니다. 전체 복잡도는 O(n^2)쯤 될 거 같고요.


그러면 선분과 선분은 중요한 게 무엇일까요? 시작점과 끝점이겠죠..

그러면 시작점, 끝점을 저장해 놓으면 되지 않을까요? 리스트 같은 데에..

최초로 만나는 교점을 구하는 게 관건일 듯 싶네요..

댓글을 작성하려면 로그인해야 합니다.