nhs0912   1년 전

음...틀렸다고 나오는데...어떤 부분이 틀렸는지 모르겠네요.

만약 N=3 이면 

1,2,3 이라면 

sum=1*2 + 1*3 + 2*3 으로 하였습니다. 

저의 알고리즘 문제점이 무엇일까요? 제 눈에는 보이지 않네요.

혹시 입력값이 N=3 인데 

1 2 3 4 가 입력 되었을때 문제가 있나해서 Scanner 로도 해보았는데 틀렸네요..그 문제는 아닌거 같아요..ㅠㅠ 


그리고 혹시 제 경우에는 for문이 2개 라서 O(N^2) 시간복잡도가 나오는데 혹시 더 빠르게 할 수 있는 팁이 있으면 알려주셨으면 감사하겠습니다^^ 


koosaga   1년 전

정답의 범위가 최대 10^18이기 때문에 overflow가 납니다. 


말씀하신대로 그걸 고쳐도 TLE가 날 건데, 한번 sum(i) = a(i) + sum(i-1) 이라는 부분합 배열을 만들어 보세요. 저걸 써서 루프 하나를 없앨 수 있습니다. 

nhs0912   1년 전

답변 너무 감사합니다^^ 

int sum 을 long 형 으로 바꾸었더니 되었네요! 

한가지 더 물어볼게 있는데요. 

sum(i) = a(i) + sum(i-1)

죄송하지만 이 부분을 좀 더 자세히 알려주실 수 있나요?? 이해가 잘 안되네요 ㅠㅠ 

koosaga   1년 전

sum(i) = a1 + a2 + ... ai 라고 생각해봅시다.

그렇다면, sum(0) = 0, sum(i) = sum(i-1) + ai로 sum 배열을 O(n)에 계산할 수 있습니다.

이제 모든 i < j에 대해서 ai * aj를 합해야 하니

이는 모든 i에 대해서 (a1 + a2 + ... + a(i-1)) * ai 를 더하는 것과 같고

즉 sum(i-1) * ai를 더하는 것과 같습니다.

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