11399번 - 그리디 알고리즘
문제
인하은행에는 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가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.
알고리즘 구현
- 사람의 수를 받는다.
- 한사람덩 시간을 받는다.
- [2, 5, 1, 4, 3]
- 사람의 순서를 말한다.
. 2번째 사람은 1분이 걸린다.
. 5번째 사람은 2분이 걸린다.
. 1번째 사람은 3분이 걸린다.
. 4번째 사람은 3분이 걸린다.
. 3번째 사람은 4분이 걸린다.
코드
num = int(input())
li = list(map(int, input().split()))
hap = 0
li.sort()
for i in range(1, num+1):
hap += sum(li[0:i])
print(hap)- 우선, 입력으로 정수
num과 공백으로 구분된 정수 리스트li를 받습니다. - 입력받은 리스트
li를 정렬합니다. - 변수
hap를 0으로 초기화합니다. 이 변수는 누적된 합을 저장할 용도로 사용됩니다. - 반복문을 통해
i가 1부터num까지 변화하는 동안 다음 작업을 수행합니다.li의 첫 번째부터i번째까지의 요소를sum함수를 사용하여 합산합니다.- 합산한 값을
hap에 누적하여 더합니다.
- 반복문이 종료된 후, 변수
hap에는 리스트li의 각 부분합이 누적된 값이 저장됩니다. - 최종적으로
hap값을 출력합니다.
예를 들어, 입력으로 num = 5, li = [3, 1, 4, 2, 5]가 주어진다고 가정해봅시다.
- 리스트
li를 정렬하면[1, 2, 3, 4, 5]가 됩니다. i가 1일 때,li의 첫 번째 요소 1을 합산하여hap에 더합니다. 따라서hap은 1입니다.i가 2일 때,li의 첫 번째 요소 1과 두 번째 요소 2를 합산하여hap에 더합니다. 따라서hap은 4입니다.i가 3일 때,li의 첫 번째 요소 1, 두 번째 요소 2, 세 번째 요소 3을 합산하여hap에 더합니다. 따라서hap은 7입니다.i가 4일 때,li의 첫 번째 요소 1, 두 번째 요소 2, 세 번째 요소 3, 네 번째 요소 4를 합산하여hap에 더합니다. 따라서hap은 11입니다.i가 5일 때, `li
