juyoung0609   3년 전

작동 횟수별로 최대로 이동할 수 있는 거리가 정해져 있고 입력으로 주어지는 거리를 이동할 수 있는지 확인하는 로직이 이 문제의 정석 풀이인 것 같습니다.

문제에서 입력으로 주어지는 거리의 최댓값이 x=0,y=231-1일 때 d=231-1로 최대가 됍니다. 이 값을 만족하게 하는 작동 횟수는 50000이하입니다.

(작동 횟수별로 이동할 수 있는 거리의 최댓값: 2*({공차가 1이고 항의 개수가 N인 등차수열의 합}), N: 작동횟수)

N이 50000일 때 이동할 수 있는 거리의 최댓값은 2*12억정도

물론 작동 횟수가 짝수인지, 홀수인지에 따라 다르지만 디테일한 부분은 작성하지 않았습니다.

작동 횟수를 1부터 증가시켜서 이동할 수 있는 거리인지 확인할 수 있고 이때 시간복잡도는 O(N),N=50000입니다.

문제에는 쿼리가 총 T개 존재한다고 하니까 전체 코드의 시간복잡도는 O(T*N)이 되고 T*N이 10000000이상이 되면 TLE를 받게 됄 것입니다.

최악의 경우 N은 50000이므로 T가 200보다 크다면 TLE를 받게 됩니다.

이 때 작동 횟수를 구하는 알고리즘을 이분탐색으로 시간을 줄일 수 있지만 알고리즘 분류를 보면 수학만 있는데 이분탐색 알고리즘을 의도한 것은 아닌 것으로 보입니다.

https://www.acmicpc.net/board/view/23033#comment-49324

이 글을 보면 T의 값이 코드를 짜는 데에 영향을 주지 않는 경우 T가 주어지지 않았을 수 있다고 하는데

T의 값에 따라 알고리즘이 달라집니다. 또한 T의 가능한 범위가 확실하게 크면 괜찮을 것 같지만 200정도로 애매하다고 생각하여 이 부분 명시를 해주셨으면 합니다.

혹시 몰라 아래에 코드 올려두겠습니다.

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