rlawjdgus246   4년 전

어떤 부분이 문제인지 정확히 모르겠습니다...
한번만 도와주세요...ㅠ

yclock   4년 전

답이 될 수 있는 최댓값은 int형 변수가 저장할 수 있는 수의 범위를 벗어납니다.

N = 105개의 수가 모두 104인 경우를 고려해주세요.

chw0501   4년 전

int형으로 풀면 overflow가 납니다

하지만 그걸 바꾸더라도 시간초과가 날거같네요

rlawjdgus246   4년 전

시간초과 나네요....

어떤 점을 봤을때 시간초과 난다고 생각하시는지 여쭤봐도 될까요??!

chw0501   4년 전

시간 제한이 1초라고 하먄 기본 연산이 대략 10^9번까지가 한계인 셈인데 본 알고리즘은 이중포문에서 연산의 횟수가 최대 n^2~10^10 입니다. 시간복잡도가 O(N^2)이죠.

yclock   4년 전

제시하신 코드의 18번째 줄부터 23번째 줄까지만 생각해볼 때, 21번째 줄의 덧셈 연산이 시행되는 횟수는 대략 N2/2입니다.

N = 105일 때, 이는 1초안에 돌기 힘들 정도로 많은 연산량이죠.

rlawjdgus246   4년 전

와우.. 시간복잡도에 대해서 공부를 한번 해봐야겠네요..

감사합니다!

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