Lv.1arraydpmath
회전 진열대의 최고 점수
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
가게의 회전 진열대에 상품 n개가 원형으로 놓여 있고, 0번 칸부터 차례로 놓인 상품의 가치가 배열 nums입니다. 진열대에서 i번 칸은 손님 눈에 띄는 정도가 i이므로, 진열대 전체의 점수는
입니다(v_i는 i번 칸에 놓인 상품의 가치).
진열대를 한 번 돌리면 모든 상품이 오른쪽으로 한 칸씩 움직이고, 마지막 칸의 상품은 0번 칸으로 옵니다. 진열대를 0번 이상 원하는 만큼 돌릴 수 있을 때, 얻을 수 있는 점수의 최댓값을 반환하세요.
입출력 예
| nums | result |
|---|---|
[4, 3, 2, 6] | 26 |
[100] | 0 |
[-1, -2, 3] | 4 |
입출력 예 설명
예 1 — 돌린 횟수에 따른 점수는 다음과 같습니다.
| 돌린 횟수 | 배치 | 점수 |
|---|---|---|
| 0 | [4, 3, 2, 6] | |
| 1 | [6, 4, 3, 2] | |
| 2 | [2, 6, 4, 3] | |
| 3 | [3, 2, 6, 4] |
예 2 — 상품이 하나뿐이면 0번 칸에 놓이므로 점수는 0입니다.
예 3 — 그대로 두면 [-1, -2, 3]의 점수가 , 한 번 돌린 [3, -1, -2]는 , 두 번 돌린 [-2, 3, -1]은 입니다. 돌리지 않는 것이 가장 좋습니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(nums: int[]) → long
제한 사항
-
nums.length -
nums[i] - 답은 32비트 정수 범위를 넘을 수 있습니다. 64비트 정수(
long)를 사용하세요.
기대 복잡도
- 시간
- O(N)
- 공간
- O(1)
입출력 예
| nums | 기대 출력 |
|---|---|
[4,3,2,6] | 26 |
[100] | 0 |
[-1,-2,3] | 4 |
힌트
힌트
k번 돌렸을 때의 점수를 , 전체 합을 라고 합시다. 한 번 더 돌리면
- 마지막 칸이 아닌 상품은 모두 한 칸씩 오른쪽으로 가므로 점수가 그 상품들의 가치 합만큼 늘어납니다.
- 마지막 칸(
n - 1번)에 있던 상품x는 0번 칸으로 가므로 만큼 줄어듭니다.
정리하면
이고, k번 돌렸을 때 마지막 칸에 있는 상품은 nums[n - 1 - k]입니다. 을 한 번 계산한 뒤 이 식으로 을 차례로 구하면서 최댓값을 고르세요.
복잡도 목표
돌릴 때마다 점수를 처음부터 다시 계산하면 으로 시간 초과입니다. 점화식을 쓰면 입니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1204 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 10 | 판정만 |
| performance | 60 | 3 | 판정만 |