백준 11399번 : ATM (python)

기다리는 시간의 합을 최소화하는 문제

1. 문제

2. 아이디어

• 사람들이 줄을 섰을 때, 뒷 번호 사람일수록 앞 사람의 소요시간을 축적한 만큼 많이 기다리게 되므로
• 기다리는 시간이 짧은 사람부터 줄을 세우는 것이 유리하다.

# 입력 받은 값을 sort() 함수를 사용해 오름차순 정렬

n = int(input()) # 사람 수
time = list(map(int, input().split())) # 기다리는 시간 
time.sort() # 오름차순 정렬 

• 그리고 한 사람 씩 기다리는 시간을 구해 모두 더한다.
• 이것을 이해하기 쉽게 그림으로 그리면 다음과 같다.

• 검정 글씨 : i 번째 사람의 소요 시간

• 빨간 글씨 : i 번째 사람이 기다려야하는 총 시간 (회색 그래프)

• 위와 같은 문제는 2중 for 반복문을 통해 쉽게 구할 수 있다.

• i번째 사람의 기다리는 시간을 구할땐, 0번 부터 i번째 사람까지의 소요시간을 모두 더하면 된다.

• 이를 코드로 나타내면 아래와 같다

delay = 0 # 총 소요시간

for i in range(n): # 만약 i=4라면,
	# j는 time[0]~time[4] 를 더하게 됨 
    for j in range(i+1): 
        delay += time[j]


print(delay)

3. 코드

n = int(input())
time = list(map(int, input().split()))
time.sort()


delay = 0

for i in range(n): 
    for j in range(i+1):
        delay += time[j]


print(delay)

추가

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

peoples.sort()  
answer = 0 

for x in range(1, n+1):
    answer += sum(peoples[0:x]) 
print(answer)