[Baekjoon] 백준 알고리즘: 11399번- ATM

1. 문제

www.acmicpc.net/problem/11399

11399번: ATM

2. 내가 생각했던 풀이과정

이 문제는 그리디 문제이다. 그리디라고 생각한 이유는 다음과 같다. 

그리디 알고리즘이란 매 순간마다 최적의 선택을 하여 정해진 목표까지 계산해 나가는 것이다.

탐욕 알고리즘은 순간순간 최적의 경우만 저장하여 최적의 수로만 진행하면 최적의 해를 구할 수 있다. 

대기하는 사람이 '가장 작은 순서'로 기다리게 되면 최적의 해를 구할 수 있기 때문이다.

문제 풀이 요소중에 1명이 끝날 때까지, 기다려야하기 때문에 마치 피보나치 수열처럼 앞에 위치한 사람이 걸리는 시간 만큼이 누적되서 계속 더해지는 것을 볼 수 있다. 결국 앞에 위치해서 중복되어 더해지는 시간의 값이 최소가 되어야 하는 것이며, 결국 입력받은 사람의 배열을 작은 수 부터 오름차순으로 정렬한 뒤 소요시간을 계산해 전부 더해버리면 되는 것이다.

 

1) 사람의 수만큼 소요시간을 배열로 입력받는다 .

2) 소요되는 시간이 적은 순서대로 오름차순으로 정렬한다

3) 반복문을 돌면서 소요시간을 계산하고, 소요시간을 결과값에 더해준다. 

 

3. 나의 풀이

N = int(input())

people = list(map(int, input().split()))
result = 0

people.sort()

for i in range(0, len(people)+1):
    for j in range(0, i):
        temp = 0 # 초기화 
        temp += people[j]
        result += temp
        
print(result)

4. 다른 사람의 풀이

n=int(input())
arr = list(map(int, input().split()))
arr.sort()
min=0
for i in range(n):
    min += arr[i]*(n-i)
print(min)

5. 새로 알게된 점