[BOJ] 11399번: ATM (python)

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

💡 해결 방법

• 앞에서부터 소요 시간이 짧은 사람 순으로 들어가야 인출 시간이 최소가 된다.
• 따라서 입력받은 소요 시간을 오름차순 정렬을 하여 문제를 해결한다.
• 인출 시간의 합을 구하기 위해 for문을 사용하였다.
  
  
  

📌 InsertionSort

• 알고리즘

  1. 현재 index에 있는 데이터 값 선택
  2. 선택한 데이터가 정렬 범위에서 삽입될 위치 탐색
  3. 삽입 위치부터 정렬 범위를 shift
  4. 삽입 위치에 선택한 데이터 삽입
  5. 모두 정렬될 때까지 1-5 반복

• 시간 복잡도 줄이기 : 삽입 위치 탐색 시 이진 탐색 등의 탐색 알고리즘 사용

• 삽입 정렬 시간복잡도 : O(n^2)
  
  

🖥️ 코드

import sys

N = int(sys.stdin.readline())
time = list(map(int, sys.stdin.readline().split()))
time.sort()
#[1, 2, 3, 4, 5]
result = 0
for i in range(N):
    result += (N-i)*time[i]

print(result)

• 정석

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
S = [0]*N

for i in range(1, N):
	insert_point = i
	insert_value = A[i]
    for j in range(i-1, -1, -1):
        if A[j] < A[i]:
            insert_point = j+1
            break
        if j == 0:
            insert_point = 0
    for j in range(i, insert_point, -1):
        A[j] = A[j-1]
    A[insert_point] = insert_value

S[0] = A[0]
for i in range(1, N):
    S[i] = S[i-1]+A[i]
sum = 0
for i in range(0, N):
    sum += S[i]

print(sum)

✏️ 알고리즘 분류

• 그리디 알고리즘
• 정렬