Python으로 지폐 교환 최소 시간 찾기 – 계산원 줄 계산 알고리즘

문제 개요

n명의 계산원(캐셔)이 지폐를 교환해 주고 있는 상황을 가정해 보겠습니다. 현재 i번째 계산원 앞에는 k[i]명의 손님이 줄을 서서 기다리고 있으며, i번째 계산원 줄에 서 있는 j번째 손님은 m[i][j]장의 지폐를 들고 있습니다. 이때 새로 줄을 서려는 사람이 자신의 지폐를 가장 빨리 교환받으려면 어느 계산원을 선택해야 할까요? 즉, 지폐를 교환받는 데 걸리는 최소 시간을 구하는 것이 이 문제의 목표입니다.

시간 계산 규칙은 다음과 같습니다.

• 계산원이 지폐 1장을 스캔하는 데 5초가 걸립니다.
• 한 명의 손님에 대한 모든 지폐 스캔이 끝나면, 지폐를 실제로 교환하는 데 15초가 추가로 걸립니다.

입력 예시

예를 들어 입력이 다음과 같다고 합시다.

n = 6
k = [12, 12, 12, 12, 12, 12]

각 계산원 줄에 서 있는 손님들이 가진 지폐 수는 아래 표와 같습니다.

출력 결과

정답은 585입니다. 그 이유는 다음과 같습니다.

• 각 손님의 지폐를 모두 스캔해야 하므로 지폐 1장당 5초씩 더합니다. 즉, 5 × m[i][j]를 누적합니다.
• 계산원이 손님 한 명을 처리할 때마다 15초가 걸리므로, 줄에 서 있던 손님 수만큼 15 × k[i]를 더합니다.
• 모든 계산원에 대해 위 값을 계산한 뒤 그중 최솟값이 곧 정답이 됩니다.

이 예시에서는 여섯 번째 계산원(인덱스 5)의 처리 시간이 가장 짧습니다. 앞에 서 있는 손님은 12명이고, 이들이 가진 지폐는 총 81장이므로 12 × 15 + 81 × 5 = 180 + 405 = 585초가 됩니다.

풀이 접근 방법

이 문제는 다음 단계로 해결할 수 있습니다.

• n := 배열 k의 크기
• minimum := 99999 (충분히 큰 초기값)
• i를 0부터 n-1까지 반복:
  • temp := k[i] × 15
  • j를 0부터 k[i]-1까지 반복하며 temp := temp + m[i][j] × 5
  • temp < minimum이면 minimum := temp로 갱신
• minimum 반환

이 알고리즘의 시간 복잡도는 O(n × k)로, 계산원 수와 각 줄의 길이에 비례하여 선형적으로 증가하므로 매우 효율적입니다.

구현 예제

아래 파이썬 코드를 통해 더 잘 이해해 보겠습니다.

def minTimeToExchange(k, m):
    n = len(k)
    minimum = 99999
    for i in range(n):
        temp = k[i] * 15          # 대기 손님 수 × 15초
        for j in range(k[i]):
            temp += m[i][j] * 5  # 각 손님의 지폐 수 × 5초
        if temp < minimum:
            minimum = temp
    return minimum

k = [12, 12, 12, 12, 12, 12]
m = [
    [7,8,9,7,9,6,10,9,9,6,7,8],
    [10,7,10,9,8,9,9,9,9,6,5,6],
    [9,8,8,9,8,6,7,9,10,6,6,7],
    [7,6,9,6,6,9,8,9,6,6,8,9],
    [9,8,7,6,5,10,8,10,7,6,6,8],
    [8,7,6,5,7,9,7,9,6,5,5,7]]
print(minTimeToExchange(k, m))

입력

k = [12, 12, 12, 12, 12, 12]
m = [[7,8,9,7,9,6,10,9,9,6,7,8],
    [10,7,10,9,8,9,9,9,9,6,5,6],
    [9,8,8,9,8,6,7,9,10,6,6,7],
    [7,6,9,6,6,9,8,9,6,6,8,9],
    [9,8,7,6,5,10,8,10,7,6,6,8],
    [8,7,6,5,7,9,7,9,6,5,5,7]]

출력

585

정리

핵심은 각 계산원마다 "대기 손님 수 × 15초 + 지폐 총 장수 × 5초"를 계산한 뒤, 그중 가장 작은 값을 선택하는 것입니다. 이처럼 단순한 완전 탐색만으로도 충분히 빠르게 최적의 계산원을 찾을 수 있으며, 실제 은행이나 마트의 대기열 최적화 문제에도 동일한 사고방식을 적용할 수 있습니다.