[Baekjoon, Python] 11399번 : ATM

도입

백준 단계별 풀기 그리디 알고리즘 세 번째 문제이다.

백준 11399번 문제, 입력, 출력

---

백준 11399번 입출력 예제 1

---

그리디 알고리즘

 그리디 알고리즘(탐욕 알고리즘)이란, 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다. 

 

 특징 - 1. 최적성의 원리 : 주어진 문제에 대한 최적해가 분할된 부분 문제의 최적해로 구성된다는 원리.

        - 2. 최적 해 보장 불가 

        - 3. 효율성 개선

 

그리디 알고리즘 예시 : 거스름돈 최소 동전 수

그리디 알고리즘 수행절차

 1. 해 선택 : 부분 해 집합에 추가 다음 항목 선택

                현재 상태 최적화 기준 만족 여부 확인

 2. 적합성 검증 : 새로운 부분 해 집합 조건 여부 확인

                      현재 집합이 해가 될 가능성 검사

 3. 해 검증 : 신규 구성 집합이 해인지 검사

                문제가 아니면 1번으로 돌아가서 반복

---

풀이

1. ATM기기를 이용하는 시간이 가장 짧은 사람을 앞에다 배치한다. 만약에 이용시간이 긴 사람을 앞에 배치하면 그만큼 뒷 사람들은 그 사람이 그만큼 이용하는 시간을 기다려야 한다. 또, 총 이용에 걸리는 시간만 구하면 된다. 그래서 이용시간이 있는 배열을 sort하여 처리한다. 

2. 이렇게 sort 된 배열을 for문으로 처리한다. 사용자(i_x)의 이용시간은 전사람의 이용시간(var_wait)+자기시간(x)이다. 따라서, 그 시간을 전체 이용시간(rtn)에 더해준다.  

---

코드

from sys import stdin

var_N = int(stdin.readline())
list_waiting_time = list(map(int, stdin.readline().split()))

list_waiting_time.sort()

rtn = var_wait = 0
for x in list_waiting_time:
    var_wait += x
    rtn += var_wait

print(rtn) 

---

마무리

 이번 문제에서 만약 총 걸리는 시간이 아닌, 누군가가 얼만큼 사용한다는 등의 특정이 필요하다면, 배열의 구성이 단순히 이용시간만을 가진 배열이 아닌, '누가' 라는 부분이 더 추가되어야 할 것이다.