관람차에 객실이 4개 있고, 각 객실에는 승객 4명씩 탑승할 수 있다고 가정해 보겠습니다. 관람차는 반시계 방향으로 회전하며, 한 번 회전할 때마다 'run'만큼의 운영 비용이 발생합니다. 배열 'cust'에는 n개의 값이 담겨 있으며, i번째 값은 i번째 회전 직전에 탑승을 기다리는 사람의 수를 나타냅니다. 승객은 탑승할 때마다 'board'만큼의 요금을 지불하며, 이 요금은 반시계 방향 한 번의 회전에 해당하는 금액입니다. 또한 대기 줄에 있는 사람들은 어느 객실에든 빈자리가 있다면 더 이상 기다리게 해서는 안 됩니다.
그렇다면 주어진 데이터를 바탕으로, 이익을 최대화하는 데 필요한 최소 회전 횟수를 구해야 합니다.
예제로 이해하기
입력이 cust = [6, 4], board = 6, run = 4라고 가정하면, 출력은 3이 됩니다.
- 처음에는 6명이 대기 중입니다. 앞의 4명이 첫 번째 객실에 탑승하고, 나머지 2명은 다음 객실을 기다립니다.
- 관람차가 회전하여 두 번째 객실이 도착합니다. 그사이 대기줄에 4명이 새로 줄을 섭니다. 따라서 기다리고 있던 4명이 두 번째 객실에 탑승합니다.
- 관람차가 다시 회전하면, 남은 3명의 고객이 세 번째 객실에 탑승합니다.
즉, 모든 고객을 처리하는 데 필요한 최소 회전 횟수는 3번입니다. 이때 얻을 수 있는 최대 이익은 (10 × 6) − (3 × 4) = 48입니다.
풀이 접근 방법
이 문제는 회전을 한 번씩 시뮬레이션하면서 누적 이익을 추적하는 방식으로 해결할 수 있습니다. 단계별 절차는 다음과 같습니다.
- res := -1 (결과로 반환할 회전 횟수)
- mst := 0 (지금까지의 최대 누적 이익)
- tmp := 0 (현재 누적 이익)
- wt := 0 (현재 대기 인원)
- cust의 각 인덱스 idx와 값 val에 대해 반복합니다.
- wt := wt + val
- chg := min(4, wt) — 이번 회전에서 태울 수 있는 인원
- wt := wt - chg
- tmp := tmp + chg * board - run — 이번 회전의 이익을 누적
- 만약 mst < tmp라면
- res := idx + 1
- mst := tmp
- x := wt / 4 (몫), y := wt mod 4 (나머지)
- 만약 4 * board > run이라면 (꽉 찬 객실 하나를 돌리는 것이 이득이라면)
- res := res + x
- 만약 y * board > run이라면 (남은 인원을 태우는 것이 이득이라면)
- res := res + 1
- res를 반환합니다.
핵심 아이디어는 입력으로 주어진 시점마다 회전을 진행하면서 누적 이익이 가장 커지는 순간을 기록하고, 이후 남은 대기 인원에 대해서는 추가 회전이 이익이 되는 경우에만 회전 횟수를 늘리는 것입니다.
구현 예제
더 잘 이해하기 위해 다음 파이썬 구현을 살펴보겠습니다.
def solve(cust, board, run):
res = -1
mst = 0
tmp = 0
wt = 0
for idx, val in enumerate(cust):
wt += val
chg = min(4, wt)
wt -= chg
tmp += chg * board - run
if mst < tmp:
res, mst = idx+1, tmp
x, y = divmod(wt, 4)
if 4 * board > run:
res += x
if y * board > run:
res += 1
return res
print(solve([6,4], 6, 4))
입력
[6,4], 6, 4
출력
3