Lv.1arraymathprefix-sum
모든 두 사람의 호흡 점수
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
동아리 회원들의 실력이 배열 skill로 주어집니다. 서로 다른 두 회원 i < j가 짝을 이루면 두 사람의 호흡 점수는 skill[i] × skill[j]입니다.
가능한 모든 두 사람 쌍의 호흡 점수를 더한 값을 반환하세요. 답이 매우 커질 수 있으므로 로 나눈 나머지를 반환합니다.
입출력 예
| skill | result |
|---|---|
[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 — 을 로 나눈 나머지는 49입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(skill: int[]) → int
제한 사항
-
skill.length -
skill[i] - 답은 로 나눈 나머지입니다.
기대 복잡도
- 시간
- O(N)
- 공간
- O(1)
입출력 예
| skill | 기대 출력 |
|---|---|
[1,2,3] | 11 |
[4,0,5,1] | 29 |
[1000000000,1000000000] | 49 |
힌트
힌트
j를 고정하면, j가 앞사람들과 만드는 점수의 합은
입니다. 왼쪽부터 훑으면서 지금까지의 합 하나만 유지하면 각 j의 몫을 바로 더할 수 있습니다. 나머지를 취한 합과 skill[j]의 곱은 근처까지 커지므로 64비트 정수로 계산하고 매번 나머지를 취하세요.
(전체 합의 제곱에서 제곱의 합을 빼고 2로 나누는 방법도 있지만, 나머지 연산 아래에서 2로 나누려면 모듈러 역원이 필요합니다.)
복잡도 목표
모든 쌍을 직접 곱하면 으로 시간 초과입니다. 누적 합을 쓰면 입니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1000 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 10 | 판정만 |
| performance | 60 | 3 | 판정만 |