Funcia
Lv.1arraydpmath

회전 진열대의 최고 점수

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

가게의 회전 진열대에 상품 n개가 원형으로 놓여 있고, 0번 칸부터 차례로 놓인 상품의 가치가 배열 nums입니다. 진열대에서 i번 칸은 손님 눈에 띄는 정도가 i이므로, 진열대 전체의 점수는

F=0⋅v0+1⋅v1+⋯+(n−1)⋅vn−1F = 0 \cdot v_0 + 1 \cdot v_1 + \dots + (n-1) \cdot v_{n-1}

입니다(v_i는 i번 칸에 놓인 상품의 가치).

진열대를 한 번 돌리면 모든 상품이 오른쪽으로 한 칸씩 움직이고, 마지막 칸의 상품은 0번 칸으로 옵니다. 진열대를 0번 이상 원하는 만큼 돌릴 수 있을 때, 얻을 수 있는 점수의 최댓값을 반환하세요.

입출력 예

numsresult
[4, 3, 2, 6]26
[100]0
[-1, -2, 3]4

입출력 예 설명

예 1 — 돌린 횟수에 따른 점수는 다음과 같습니다.

돌린 횟수배치점수
0[4, 3, 2, 6]0⋅4+1⋅3+2⋅2+3⋅6=250 \cdot 4 + 1 \cdot 3 + 2 \cdot 2 + 3 \cdot 6 = 25
1[6, 4, 3, 2]0+4+6+6=160 + 4 + 6 + 6 = 16
2[2, 6, 4, 3]0+6+8+9=230 + 6 + 8 + 9 = 23
3[3, 2, 6, 4]0+2+12+12=260 + 2 + 12 + 12 = 26

예 2 — 상품이 하나뿐이면 0번 칸에 놓이므로 점수는 0입니다.

예 3 — 그대로 두면 [-1, -2, 3]의 점수가 1⋅(−2)+2⋅3=41 \cdot (-2) + 2 \cdot 3 = 4, 한 번 돌린 [3, -1, -2]는 −1−4=−5-1 - 4 = -5, 두 번 돌린 [-2, 3, -1]은 3−2=13 - 2 = 1입니다. 돌리지 않는 것이 가장 좋습니다.

효율성

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

함수 시그니처

solution(nums: int[]) → long

제한 사항

  • 1≤1 \le nums.length ≤200,000\le 200{,}000
  • −106≤-10^6 \le nums[i] ≤106\le 10^6
  • 답은 32비트 정수 범위를 넘을 수 있습니다. 64비트 정수(long)를 사용하세요.

기대 복잡도

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

입출력 예

nums기대 출력
[4,3,2,6]26
[100]0
[-1,-2,3]4

힌트

힌트

k번 돌렸을 때의 점수를 F(k)F(k), 전체 합을 SS라고 합시다. 한 번 더 돌리면

  • 마지막 칸이 아닌 상품은 모두 한 칸씩 오른쪽으로 가므로 점수가 그 상품들의 가치 합만큼 늘어납니다.
  • 마지막 칸(n - 1번)에 있던 상품 x는 0번 칸으로 가므로 (n−1)⋅x(n-1) \cdot x만큼 줄어듭니다.

정리하면

F(k+1)=F(k)+S−n⋅xF(k+1) = F(k) + S - n \cdot x

이고, k번 돌렸을 때 마지막 칸에 있는 상품은 nums[n - 1 - k]입니다. F(0)F(0)을 한 번 계산한 뒤 이 식으로 F(1),F(2),…,F(n−1)F(1), F(2), \dots, F(n-1)을 차례로 구하면서 최댓값을 고르세요.

복잡도 목표

돌릴 때마다 점수를 처음부터 다시 계산하면 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 251204 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

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

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