zihasoo   10달 전

최대 파이어볼 개수 m: 50 * 50

최대 명령 횟수 k: 1,000

최대 속력 s: 1,000 

저는 "모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다" 라는 부분을 단순하게 구현하여 s만큼 반복문을 돌려서 이동하도록 만들었습니다.

이때 모든 파이어볼이 이동 후 제자리로 돌아온다고 하면, 2,500개의 파이어볼이 1,000칸 이동하는 연산을 1,000번 반복하므로 총 계산량이 2,500,000,000이 나오는데, 어떻게 시간 초과가 나오지 않은 것인지 모르겠습니다. 제가 뭔가 잘못 계산한 것이 있는 걸까요?

움직이는 함수 구현은 아래와 같습니다

https://www.acmicpc.net/board/...

저도 사실 1초에 1억 번 연산한다 가정하고 문제를 풀기는 하지만, 연산을 한 번에 얼마나 하냐에 따라 달라지는 듯합니다.


https://www.acmicpc.net/proble...

TMI로, 이 문제를 참고할 수 있을 듯합니다.

이걸 O(NQ)에 구현하면 N은 3000이고 Q는 100000이니까 3억 번 연산한다고 생각할 수 있는데요.

실제로는 시간 제한이 2초인 데도 불구하고 O(NQ)에 구현해도 시간 초과를 받지 않습니다.

zenith82114   10달 전

더하기와 빼기는 초당 10억 번 이상도 충분합니다.

zihasoo   10달 전

널널하게 잡아도 25억번은 너무 많다고 생각했는데 저게 되네요.... 컴퓨터는 위대하군요

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