kei890   4년 전

제가짠 코드는 이건데요

어디부분에서 시간초과가 왜뜨는지 잘모르겠습니다.

알려주시면 감사하겠습니다.

설날 모두 잘보내세요~

chogahui05   4년 전

x, y는 2^31까지 입력받을 수 있겠군요.

이동 거리가 1씩 계속 증가한다고 가정하면 시간 복잡도는 루트 d이군요. d는 최대 2^31이므로 (2^31)^1/2 = 2^15 * 1.414... = 46340이네요.

이건 어디까지나 최악의 경우 arr[2]를 더하는 횟수이고요. 하나의 단위계산을 하기 위해서

(1) while(1) 조건 검사

(2) Distance가 arr의 특정 원소보다 큰지 검사.

(3) arr[0]부터 arr[2]까지 원소값을 1씩 증가시킨다.


테스트 케이스가 몇 개일지도 모르는 상황에서, 한 케이스당, 최악일 때, 46000번 단위계산을 한다면 시간초과가 날 거 같습니다.

규칙을 조금만 더 유추해 보세요.

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