그리디 알고리즘 : ATM(백준 11399번)

▶ 문제 : https://www.acmicpc.net/problem/11399

11399번: ATM

##### 문제 #####
# 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다.
# 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.
# 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다.
# 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자.
# [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다.
# 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다.
# 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하다.
# 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다.
# 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.
# 줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면,
# 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분,
# 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다.
# 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다.
# 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.
# 줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때,
# 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

##### 입력 #####
# 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다.
# 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

##### 출력 #####
# 첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

 

▶ 접근 방법

시간을 오름차순으로 정렬하고, 단계 별로 해당 시간을 모두 더해줄 때 요구 사항을 충족할 수 있다.

 

▶ 풀이 코드

import sys

N = int(sys.stdin.readline().rstrip())
time_info = sorted(list(map(int, sys.stdin.readline().split())))

result = 0
prev_num = 0
for i in range(N):
    result += (prev_num + time_info[i])
    prev_num += time_info[i]

print(result)

 

▶ 관련 링크

2021.11.27 - [알고리즘] - 그리디 알고리즘(Greedy Algorithm)이란?

2021.11.27 - [알고리즘] - 그리디 알고리즘 : 동전 0(백준 11047번)

2021.11.27 - [알고리즘] - 그리디 알고리즘 : 잃어버린 괄호(백준 1541번)

2021.11.27 - [알고리즘] - 그리디 알고리즘 : 회의실 배정(백준 1931번)

2021.11.27 - [알고리즘] - 그리디 알고리즘 : 신입사원(백준 1946번)

2021.11.27 - [알고리즘] - 그리디 알고리즘 : 멀티탭 스케줄링(백준 1700번)

2021.12.01 - [알고리즘] - 그리디 알고리즘 : 주식(백준 11501번)