Funcia
Lv.1arraymathprefix-sum

모든 두 사람의 호흡 점수

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

동아리 회원들의 실력이 배열 skill로 주어집니다. 서로 다른 두 회원 i < j가 짝을 이루면 두 사람의 호흡 점수는 skill[i] × skill[j]입니다.

가능한 모든 두 사람 쌍의 호흡 점수를 더한 값을 반환하세요. 답이 매우 커질 수 있으므로 1,000,000,0071{,}000{,}000{,}007로 나눈 나머지를 반환합니다.

입출력 예

skillresult
[1, 2, 3]11
[4, 0, 5, 1]29
[1000000000, 1000000000]49

입출력 예 설명

예 1 — 쌍은 (1, 2), (1, 3), (2, 3)이고 점수는 2 + 3 + 6 = 11입니다.

예 2 — 4×0 + 4×5 + 4×1 + 0×5 + 0×1 + 5×1 = 0 + 20 + 4 + 0 + 0 + 5 = 29입니다.

예 3 — 101810^{18}을 1,000,000,0071{,}000{,}000{,}007로 나눈 나머지는 49입니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(skill: int[]) → int

제한 사항

  • 2≤2 \le skill.length ≤200,000\le 200{,}000
  • 0≤0 \le skill[i] ≤109\le 10^9
  • 답은 1,000,000,0071{,}000{,}000{,}007로 나눈 나머지입니다.

기대 복잡도

시간
O(N)
공간
O(1)

입출력 예

skill기대 출력
[1,2,3]11
[4,0,5,1]29
[1000000000,1000000000]49

힌트

힌트

j를 고정하면, j가 앞사람들과 만드는 점수의 합은

skill[0]⋅skill[j]+⋯+skill[j−1]⋅skill[j]=(skill[0]+⋯+skill[j−1])×skill[j]\text{skill}[0] \cdot \text{skill}[j] + \dots + \text{skill}[j-1] \cdot \text{skill}[j] = (\text{skill}[0] + \dots + \text{skill}[j-1]) \times \text{skill}[j]

입니다. 왼쪽부터 훑으면서 지금까지의 합 하나만 유지하면 각 j의 몫을 바로 더할 수 있습니다. 나머지를 취한 합과 skill[j]의 곱은 101810^{18} 근처까지 커지므로 64비트 정수로 계산하고 매번 나머지를 취하세요.

(전체 합의 제곱에서 제곱의 합을 빼고 2로 나누는 방법도 있지만, 나머지 연산 아래에서 2로 나누려면 모듈러 역원이 필요합니다.)

복잡도 목표

모든 쌍을 직접 곱하면 O(N2)O(N^2)으로 시간 초과입니다. 누적 합을 쓰면 O(N)O(N)입니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251000 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4010판정만
performance603판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.