본문으로 건너뛰기

[11399] ATM

링크 : https://www.acmicpc.net/problem/11399

1. 문제 분석​

접근 방식: 정렬

시간 복잡도: O(Nlog⁡N)O(N \log N)

2. Python 풀이​

import sys

input = sys.stdin.readline

n = int(input())
P = list(map(int, input().split()))

P.sort()

total_waiting_time = 0
temp_sum = 0

for time in P:
    temp_sum += time
    total_waiting_time += temp_sum

print(total_waiting_time)

Insertion Sorting Version​

import sys

input = sys.stdin.readline

n = int(input())
P = list(map(int, input().split()))

# Insertion Sort
for i in range(1, n):
    insert_point = i
    insert_value = P[i]
    
    # 위치 찾기
    for j in range(i-1, -1, -1):
        if P[j] < P[i]:
            insert_point = j + 1
            break
        if j == 0:
            insert_point = 0
            
    # 데이터 뒤로 밀기 (Shifting)
    for k in range(i, insert_point, -1):
        P[k] = P[k-1]
        
    P[insert_point] = insert_value

# 총 대기 시간 합산 (누적 합)
total_sum = 0
current_cumulative_sum = 0

for time in P:
    current_cumulative_sum += time
    total_sum += current_cumulative_sum

print(total_sum)

3. 학습 내용​

새로 알게 된 점: Insertion Sort 구현

4. 관련 개념​

Tags