BOJ 2259 두더지 잡기

좌표상에서 두더지가 어떤 시간 T에 어떤 좌표에 출몰하는데, 1초당 S만큼 이동할 수 있는 두더지 사냥꾼이 좌표(0, 0)에서 출발해서 최대 몇 마리의 두더지를 잡을 수 있는지 구하는 문제이다.
모든 경우를 다 해봐야할 것 같다. 하지만 그러면 너무 경우가 많으니 dp로 풀어야 한다.
d[x][y] = (x, y)의 두더지를 잡으면서 시작할 때, 잡을 수 있는 두더지의 최대 마리수
로 하면... 문제가... (x, y)이전에 어떤 두더지를 잡으면서 왔냐에 따라 d[x][y]가 영향받기 때문에... 그럼 시간도 넣어야 하나? d[x][y][T] = (시간 T에 (x, y)를... 아 ... 다시 생각해보자.
일단 (x, y)의 두더지를 잡으려면 그 두더지가 출몰하는 시간 T에만 잡을 수 있다. 즉, (x, y)의 두더지를 잡은 후에는 시간 T이후에 출몰하는 두더지들만 잡을 수 있는 것이다.
그러니까 아까 고민했던 (x, y)이전에 어떤 두더지를 잡으면서 왔냐에 따라 d[x][y]가 영향을 받는다는 것은, (x, y)이전에 어떤 두더지를 잡으면서 왔냐에 따라 앞으로 잡을 수 있는 두더지가 변할 수 있다는 것이었는데, 두더지는 무조건 시간 T! 딱 그 순간에만 잡을 수 있으므로 (x, y)의 두더지가 출몰하는 시간 T이전에는 시간 T이후의 두더지를 잡을 수 없다.
그러니까... 나는 시간 T이하?로 착각했던 것 같다. 그러므로 그냥 d[x][y]로 해도 될 것이다.
하지만 이럴 경우 x, y값이 최대 1000이므로 두더지는 최대 6666마리이므로 시간복잡도상으로 O(1000*1000*6666)..가 나올 수 있어보이는데... 음 (x, y)는 좌표고 결국 이 좌표는 6666개 있으므로 즉 두더지는 최대 6666마리이므로 각 좌표마다 번호를 부여해서
d[x] = x번 두더지를 잡으면서 시작할 때, 잡을 수 있는 두더지의 최대 마리수
로 놓으면 될 것 같다.
d[x] = max(nextX는 xT이후에 시간 안에 도달 가능한 곳만.. | d[nextX]+1) 이 될 것 같은데,
아예 미리 시간 T기준으로 정렬을 해놓으면 편할 것 같다.

조금 까다롭다고 생각되는 부분이 어떤 좌표에서 어떤 좌표로 이동할 때, 실수만큼의 시간이 걸린다는 것인데 일단 실수 계산으로 인한 오차가 영향을 줄 정도의 데이터 개수는 아닌 것 같으니... 그냥 double형으로 놓고 해보려고 한다.

구현해보자. AC를 받았다.
고수님들의 코드를 보니 대부분 for문으로 구현하신 것 같고,
일단 두 좌표간의 거리를 계산하는 부분에서 대각선 거리이므로 피타고라스의 정리를 이용하고 제곱과 sqrt연산이 필요해서 코드가 길어지는데, 이 부분에서 곱셈 연산을 함수로 만들어서 코드를 좀 간단하게 한 방법도 있었고, 시간을 구해 비교하기 위해 거리를 속도로 나눠주는데 나눌 필요없이 상대편 시간과 속도를 곱해서 거리를 만들어서 비교해도 된다. 나눗셈이 더 느리단 말을 얼핏 들은 거 같은데 찾아보니 나눗셈 연산이 곱셈보다 더 느린 것 같다. 그러니까 저렇게 나눗셈 대신 곱셈을 쓰는 것이 더 나아보인다.
그리고 sqrt를 쓰지 않고 곱셈한 값으로만 비교한 경우도 있었는데, 이 방법은 좀 더 생각을 해봐야겠지만 좋아보인다.(시간도 시간이지만...int를 double로 형변환할 필요도 없어서 오차 없이 정확할 것 같다. 아 그 대신 long long이 필요하거나 더 커질 수도 있겠지만...)
곱셈한 값으로만 비교해서 하니 시간도 좀 줄었고, 확실히 정확해서 좋을 것 같다.

문제를 풀다보니 약간... 경찰차 문제와 비슷한 느낌을 받았다.