벽돌과 사다리로 가장 멀리
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
지붕 위를 달리는 파쿠르 선수가 일렬로 늘어선 건물 채를 왼쪽부터 차례로 건너려고 합니다. i번 건물의 높이는 heights[i]이고,
선수는 0번 건물 옥상에서 출발합니다.
i번 건물에서 i+1번 건물로 건너갈 때,
- 다음 건물이 같거나 낮으면 그냥 건너갑니다.
- 다음 건물이 더 높으면 높이 차
heights[i+1] - heights[i]만큼의 벽돌을 쌓거나, 사다리 하나를 써야 합니다.
가진 벽돌은 bricks개, 사다리는 ladders개이며 한 번 쓴 벽돌과 사다리는 다시 쓸 수 없습니다.
벽돌과 사다리를 가장 잘 나누어 쓸 때 도달할 수 있는 가장 먼 건물의 번호를 반환하세요.
입출력 예
| heights | bricks | ladders | result |
|---|---|---|---|
[4, 2, 7, 6, 9, 14, 12] | 5 | 1 | 4 |
[4, 12, 2, 7, 3, 18, 20, 3, 19] | 10 | 2 | 7 |
[14, 3, 19, 3] | 17 | 0 | 3 |
입출력 예 설명
예 1 — 2 → 7(차이 5)에 벽돌 5개, 6 → 9(차이 3)에 사다리를 쓰면 4번 건물까지 갑니다. 9 → 14는 차이가 5인데 남은 것이 없습니다.
예 2 — 4 → 12와 3 → 18에 사다리를, 2 → 7에 벽돌 5개를 쓰면 18 → 20에 벽돌 2개를 더 써서 7번 건물까지 갑니다. 3 → 19는 벽돌이 3개뿐이라 갈 수 없습니다.
예 3 — 3 → 19(차이 16)에 벽돌 16개를 쓰면 마지막 건물까지 갑니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(heights: int[], bricks: int, ladders: int) → int
제한 사항
-
heights.length -
heights[i] -
bricks -
ladders
기대 복잡도
- 시간
- O(N log N)
- 공간
- O(N)
입출력 예
| heights | bricks | ladders | 기대 출력 |
|---|---|---|---|
[4,2,7,6,9,14,12] | 5 | 1 | 4 |
[4,12,2,7,3,18,20,3,19] | 10 | 2 | 7 |
[14,3,19,3] | 17 | 0 | 3 |
힌트
힌트
어떤 지점까지 갈 수 있는지는 "지금까지 올라간 높이 차들 중 가장 큰 ladders개에는 사다리를, 나머지에는 벽돌을 쓰는 것"으로 판단할 수 있습니다.
사다리는 높이 차와 상관없이 한 번에 해결하므로 큰 차이에 쓰는 것이 이득이기 때문입니다.
매번 지금까지의 높이 차를 정렬해 확인하면 이 됩니다. 대신 사다리를 쓴 높이 차들을 최소 힙에 담아 두세요.
- 오르막을 만나면 일단 사다리를 쓴 것으로 하고 힙에 넣습니다.
- 힙 크기가
ladders를 넘으면, 힙에서 가장 작은 차이를 꺼내 벽돌로 바꿉니다. - 벽돌이 모자라면 바로 그 직전 건물이 답입니다.
전체 입니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1128 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 12 | 판정만 |
| performance | 60 | 4 | 판정만 |