13900번 - 순서쌍의 곱의 합
어떤 부분이 문제인지 정확히 모르겠습니다...한번만 도와주세요...ㅠ
답이 될 수 있는 최댓값은 int형 변수가 저장할 수 있는 수의 범위를 벗어납니다.
N = 105개의 수가 모두 104인 경우를 고려해주세요.
int형으로 풀면 overflow가 납니다
하지만 그걸 바꾸더라도 시간초과가 날거같네요
시간초과 나네요....
어떤 점을 봤을때 시간초과 난다고 생각하시는지 여쭤봐도 될까요??!
시간 제한이 1초라고 하먄 기본 연산이 대략 10^9번까지가 한계인 셈인데 본 알고리즘은 이중포문에서 연산의 횟수가 최대 n^2~10^10 입니다. 시간복잡도가 O(N^2)이죠.
제시하신 코드의 18번째 줄부터 23번째 줄까지만 생각해볼 때, 21번째 줄의 덧셈 연산이 시행되는 횟수는 대략 N2/2입니다.
N = 105일 때, 이는 1초안에 돌기 힘들 정도로 많은 연산량이죠.
와우.. 시간복잡도에 대해서 공부를 한번 해봐야겠네요..
감사합니다!
댓글을 작성하려면 로그인해야 합니다.
rlawjdgus246 4년 전
어떤 부분이 문제인지 정확히 모르겠습니다...
한번만 도와주세요...ㅠ