글 읽기 - 테스트 케이스가 빈약합니다.

조건문 :

첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

수행 시간 : 0.5초.

nlogn

n^2

N = 10000, M = 300000000, A[i] = 1 (i = 1 ~ N) 일때, n^2면 수행시간이 0.5초를 초과하게 됩니다.

"1초에 1억 번의 연산"은 절대적인 기준이 아니고, 간단한 작업은 훨씬 빠르게 수행할 수 있습니다. 실제로 실행했을 때 수행 시간이 0.5초를 넘겼나요?

문제 풀이가 0.5*n*n이면 0.5초에 아슬아슬하게 통과되더라도 문제없습니다.

죄송합니다. 당연히 n^2이면 10초, 적어도 0.5초는 초과라고 생각했는데, 제 불찰입니다.

생각보다 굉장히 적게 시간이 걸리는군요..

또 배워갑니다.

감사합니다.

10,000²은 1억입니다.

초당 천만번 아닌가요?

1억 번입니다. 사실 개인적으로는 3억 번까지로 해도 무방하다고 생각합니다.

좋은 의견 감사합니다 ^^7

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

Baekjoon Online Judge