Funcia
Lv.4convex-hull-trickdpli-chao-tree

개구리의 징검다리 점프

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

개울에 징검다리 돌 N개가 일렬로 놓여 있고, i번 돌의 높이는 h[i]입니다. 개구리는 0번 돌에서 출발해 N-1번 돌까지 가려고 합니다.

개구리는 i번 돌에서 번호가 더 큰 아무 돌 j(j > i)로나 한 번에 뛸 수 있습니다. 한 번 뛸 때마다 체력이

(h[j]−h[i])2+c(h[j] - h[i])^2 + c

만큼 듭니다. c는 점프 한 번마다 드는 고정 비용입니다.

N-1번 돌에 도착할 때까지 드는 체력의 최솟값을 반환하세요.

입출력 예

hcresult
[1, 3, 6, 10]544
[5, 1, 5]100100
[1, 1000000]0999998000001

입출력 예 설명

예 1 — 돌을 하나씩 밟으면 22+32+42+3×5=442^2 + 3^2 + 4^2 + 3 \times 5 = 44입니다. 0 → 3으로 바로 뛰면 92+5=869^2 + 5 = 86, 0 → 2 → 3은 25+16+10=5125 + 16 + 10 = 51이므로 44가 최소입니다.

예 2 — 고정 비용이 크므로 가운데 돌을 건너뛰고 0 → 2로 한 번에 가는 편이 낫습니다. 높이 차가 0이라 비용은 100100입니다.

예 3 — 답이 32비트 정수 범위를 넘을 수 있습니다.

효율성

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

함수 시그니처

solution(h: int[], c: long) → long

제한 사항

  • 2≤N=2 \le N = h.length ≤200,000\le 200{,}000
  • 1≤1 \le h[i] ≤1,000,000\le 1{,}000{,}000 (높이가 정렬되어 있다는 보장은 없습니다)
  • 0≤0 \le c ≤1012\le 10^{12}

기대 복잡도

시간
O(N log N)
공간
O(N)

입출력 예

hc기대 출력
[1,3,6,10]544
[5,1,5]100100
[1,1000000]0999998000001

힌트

힌트

dp[i] = i번 돌까지 오는 최소 비용이라 하면 dp[i] = min_{j<i} dp[j] + (h[i] - h[j])^2 + c입니다. 그대로 계산하면 O(N2)O(N^2)입니다.

제곱을 풀어 보세요.

dp[j]+(hi−hj)2=(−2hj)⏟기울기⋅hi+(dp[j]+hj2)⏟절편+hi2dp[j] + (h_i - h_j)^2 = \underbrace{(-2h_j)}_{\text{기울기}} \cdot h_i + \underbrace{(dp[j] + h_j^2)}_{\text{절편}} + h_i^2

즉 이전 돌 j마다 직선 y=(−2hj)x+(dp[j]+hj2)y = (-2h_j)x + (dp[j] + h_j^2) 하나가 생기고, dp[i]는 x=hix = h_i에서 그 직선들의 최솟값에 hi2+ch_i^2 + c를 더한 값입니다.

  • 높이가 정렬되어 있지 않으므로 기울기와 질의 위치가 단조롭지 않습니다. 직선 삽입·점 질의를 O(log⁡X)O(\log X)에 처리하는 리차오 트리(Li Chao tree)가 잘 맞습니다. 좌표는 등장하는 높이로 압축하면 됩니다.
  • 분할 정복(CDQ)으로 정렬해 단조 볼록 껍질 트릭을 쓰는 방법도 있습니다.
  • 중간값은 101210^{12} 규모가 되므로 64비트 정수를 쓰세요.

복잡도 목표

모든 이전 돌을 확인하는 O(N2)O(N^2) 풀이는 효율성 테스트에서 시간 초과가 납니다. O(Nlog⁡N)O(N \log N)이 필요합니다.

언어별 시간 제한

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

테스트 그룹

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

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