chsun0303   5년 전

python3로는 시간초과가 나서, 일단 pypy3로 통과를 하긴 했습니다.

pypy3로 통과한 코드와 동일하게 C++14로 제출을 해 봤고 시간초과가 나는 것을 확인했습니다.

다른 분들의 코드를 보고 나서 제 코드가 통과하는 게 맞는지 의문이 들었기에 질문을 하게 되었습니다.

13-14번 줄에 있는 부분은 O(n)의 시간복잡도를 가지기 때문에 시간초과가 나는게 당연하다고 생각했으며, 여기서 제가 든 생각은 아래와 같습니다.

  1. 채점 데이터 내의 n 값이 그렇게 크지 않거나, 
  2. 큰 수 연산 시 pypy3가 무지 빠르다.

제가 참고할 만한 자료가 있을까요?

chsun0303   5년 전

n, k = map(int, input().split())

r = 0
for i in range(1, n + 1):
    r += k % i
print(r)

문제에 제시 된 그대로 pypy3로 돌렸을 때, 시간초과가 나는 것을 확인했습니다.

n < k 일 때, n이 10^9인 데이터를 추가하면 될 듯 한데, 제 추측이 맞나요?

chsun0303   5년 전

t = k//2입니다.

n < k 일 때 13번 줄에 있는 for문이 돌기 때문에, 최악은 10억번을 도는게 맞지 않나요?

이미 해당 데이터가 존재한다고 하니 더 의문이 드는군요 ㅠㅠ

chsun0303   5년 전

헉 밤샜더니 제 눈이 어찌되었나 봅니다.... 감사합니다 ㅠㅠ 

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