백준 3025 돌 던지기

[문제] 백준 3025 돌 던지기

 

[알고리즘] 시뮬레이션

 

[시간복잡도] $ O(N + R) $

 

[솔루션]

일단 딱봐도 시뮬레이션을 해야한다. 하지만 단순 시뮬레이션으로 소스코드를 짠다면 $ O(NR) $로 무조건 시간초과이다.
이를 어떻게 줄일지 아이디어를 생각해봐야한다.

아이디어 1 : 돌 던졌을때 직선으로 내려가는 부분을 잘 정리하면 시간초과가 해결될 것 같다.

결론부터 말하자면 이것도 시간초과이다. 벽의 분포로 인해 돌이 지그재그로 떨어지는 경우 돌 던지는 경우마다 $ O(R) $을 갱신하기 때문에 TLE이다.

아이디어 2 : 그렇다면 지그재그로 가는 경로도 잘 정리하면 될 것 같다.

이거 또한 $O(R)$의 시간복잡도를 가질 것이다. 따라서 시간초과.

아이디어 3

그렇다면 어떻게 짜야할까? 바로, 돌 던졌을 때 그 경로를 저장하고 그 경로에서 맨 뒤(도착지점)부터 차례로 보면 된다.

1. 저장된 경로가 없을 경우 그 경로를 갱신(생성)한다.
2. 경로의 끝 부분(도착지점)을 보고 돌이 있다면 그 경로에서 돌이 없을 때까지 돌아간다.
3. 경로의 끝 부분(도착지점)에서 돌이 더 이동할 수 있는지 경로를 업데이트 해준다.
4. 그 경로의 끝 부분이 돌을 던졌을 때 도착하는 곳이다.

이게 바로 내가 생각한 아이디어 이다. $N$이나 $R$의 범위가 작은 단순 시뮬레이션이였다면 solved.ac 기준으로 골드 5 정도 될 난이도이지만, $N$, $R$의 범위가 크고 아이디어를 생각하기에 좀 어렵기 때문에 골드 1 이상으로 예상된다. (시뮬레이션 문제들은 난이도를 줄때 어렵다.. 너무 많은 고민을 하게 되는 유형)

소스코드