overpower   4년 전

<x:y> 를 찾을 때

x + m * i == y + n * j (i 와 j는 서로 다른 정수)

를 만족하는 i, j 가 i <= n , j <= m 안에 있으면 그 때의 x + m * i 값이 해당년도가 되므로, 

그 값을 출력하고, 범위를 넘어서면 -1 을 출력하도록 하였습니다. (년도 maximum이 n과m의 최소공배수이기 때문에)


i를 for로 n 번 돌고

그 각각의 i에 대하여, 위의 조건을 만족하는 j를 바이너리 서치로 log m 안에 찾으면,

n * log m 안에 찾아지는 거 아닌가요? (0 < n,m < 40000)


예제는 잘 돌아가고, 제가 임의로 큰 수를 집어 넣어도 잘 돌아가는데, 채점결과는 시간초과가 나오네요;; (설마, 테스트 케이스가 엄청 많은건가;;)


고수님들, 알려주세요!!!

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