Lv.1arraydpmath
가장 좋은 전망대 두 곳
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
등산로를 따라 전망대가 한 줄로 늘어서 있고, i번 전망대(0부터 시작)의 경치 점수는 scores[i]입니다. 하루에 전망대 두 곳 i < j를 들르려고 하는데, 두 곳이 멀수록 걷는 데 힘이 들어서 거리만큼 점수가 깎입니다.
두 전망대를 고른 점수는 다음과 같습니다.
가능한 점수의 최댓값을 반환하세요.
입출력 예
| scores | result |
|---|---|
[8, 1, 5, 2, 6] | 11 |
[1, 2] | 2 |
[1000000000, 1, 1000000000] | 1999999998 |
입출력 예 설명
예 1 — i = 0, j = 2를 고르면 입니다. i = 0, j = 4는 입니다.
예 2 — 고를 수 있는 쌍은 하나뿐이며 입니다.
예 3 — 이고, 결과가 32비트 정수 범위를 넘습니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(scores: int[]) → long
제한 사항
-
scores.length -
scores[i] - 답은 32비트 정수 범위를 넘을 수 있습니다. 64비트 정수(
long)를 사용하세요.
기대 복잡도
- 시간
- O(N)
- 공간
- O(1)
입출력 예
| scores | 기대 출력 |
|---|---|
[8,1,5,2,6] | 11 |
[1,2] | 2 |
[1000000000,1,1000000000] | 1999999998 |
힌트
힌트
식을 i에 관한 부분과 j에 관한 부분으로 나눠 보세요.
j를 왼쪽부터 하나씩 옮기면서, 지금까지 본 i < j 중 scores[i] + i의 최댓값 하나만 기억하면 됩니다. 각 j에서 그 최댓값 + scores[j] - j로 답을 갱신한 뒤, scores[j] + j로 최댓값을 갱신하세요.
복잡도 목표
모든 쌍을 확인하면 으로 시간 초과입니다. 식을 나누고 최댓값을 유지하면 입니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1038 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 10 | 판정만 |
| performance | 60 | 4 | 판정만 |