tony9402

[문제] 백준 3025 돌 던지기 [알고리즘] 시뮬레이션 [시간복잡도] $ O(N + R) $ [솔루션] 일단 딱봐도 시뮬레이션을 해야한다. 하지만 단순 시뮬레이션으로 소스코드를 짠다면 $ O(NR) $로 무조건 시간초과이다. 이를 어떻게 줄일지 아이디어를 생각해봐야한다. 아이디어 1 : 돌 던졌을때 직선으로 내려가는 부분을 잘 정리하면 시간초과가 해결될 것 같다. 결론부터 말하자면 이것도 시간초과이다. 벽의 분포로 인해 돌이 지그재그로 떨어지는 경우 돌 던지는 경우마다 $ O(R) $을 갱신하기 때문에 TLE이다. 아이디어 2 : 그렇다면 지그재그로 가는 경로도 잘 정리하면 될 것 같다. 이거 또한 $O(R)$의 시간복잡도를 가질 것이다. 따라서 시간초과. 아이디어 3 그렇다면 어떻게 짜야할까? 바로,..