[알고리즘 일기] 24. 지각 벌금 적게 내기

728x90

 

문제 24. (2021-05-24)

 

지각 벌금 적게 내기

익중이네 밴드부는 매주 수요일 오후 6시에 합주를 하는데요. 멤버들이 너무 상습적으로 늦어서, 1분에 1달러씩 내야 하는 벌금 제도를 도입했습니다. 그런데 마침 익중이와 친구 넷이 놀다가 또 지각할 위기입니다. 아직 악보도 출력해 놓지 않은 상황입니다. 어차피 같이 놀다 늦은 것이니 벌금을 다섯 명이서 똑같이 나눠 내기로 하고, 벌금을 가능한 적게 내는 방법을 고민해 보기로 합니다. 다섯 사람이 각각 출력해야 하는 페이지 수는 3장, 1장, 4장, 3장, 2장입니다. 프린터는 한 대밖에 없고, 1장을 출력하기 위해서는 1분이 걸립니다.

 

현재 순서대로 출력한다면,

첫 번째 사람: 33분 지각

두 번째 사람: 3 + 13+1분 지각

세 번째 사람: 3 + 1 + 43+1+4분 지각

네 번째 사람: 3 + 1 + 4 + 33+1+4+3분 지각

다섯 번째 사람: 3 + 1 + 4 + 3 + 23+1+4+3+2분 지각

총 39달러의 벌금을 내야 합니다.

 

이러한 방식으로 벌금을 낸다고 할 때, 최소 벌금을 리턴해주는 함수를 작성하시오.

 

 

주의사항

* 출력할 페이지 수가 담긴 리스트 pages_to_print를 파라미터로 받고 최소 벌금을 리턴해 주는 함수 min_fee를 Greedy Algorithm으로 구현하세요.

 

 

❧ 테스트 셋

def min_fee(pages_to_print):
    #Code

#Test
print(min_fee([6, 11, 4, 1]))
print(min_fee([3, 2, 1]))
print(min_fee([3, 1, 4, 3, 2]))
print(min_fee([8, 4, 2, 3, 9, 23, 6, 8]))

 

❧ 출력 예시

39
10
32
188

 

---

❧ 정답

Try 1

def min_fee(pages_to_print):
    result = 0
    # 리스트 개수 만큼 반복
    while(len(pages_to_print)):
        result += min(pages_to_print) * len(pages_to_print)
        # 리턴값에 포함시킨 요소는 남은 리스트에서 삭제
        pages_to_print.remove(min(pages_to_print))
    return result

print(min_fee([6, 11, 4, 1]))
print(min_fee([3, 2, 1]))
print(min_fee([3, 1, 4, 3, 2]))
print(min_fee([8, 4, 2, 3, 9, 23, 6, 8]))

 

1️⃣ 시간 복잡도

반복문 반복 : O(n)

최소값 구하기 : O(log2n)

∴ O(n) * O(n log2n) = O(n log2n)

 

2️⃣ 반복하며 리스트 요소 삭제

 

 

---

Try 2

def min_fee(pages_to_print):
    # 리스트 정렬 과정 추가
    sorted_list = sorted(pages_to_print)

    result = 0
    for i in range(len(sorted_list)):
        result += sorted_list[i] * (len(sorted_list) - i)
    return result

print(min_fee([6, 11, 4, 1]))
print(min_fee([3, 2, 1]))
print(min_fee([3, 1, 4, 3, 2]))
print(min_fee([8, 4, 2, 3, 9, 23, 6, 8]))

 

1️⃣ 시간 복잡도

리스트 정렬 : O(n log2n)

반복문 반복 : O(n)

∴ O(n) + O(n log2n) = O(n log2n)

 

2️⃣ 리스트 정렬 후 반복

3️⃣ 최적 부분 구조 : 가장 적은 시간이 걸리는 사람 순으로 앞에 배치

4️⃣ 탐욕적 선택 속성 : 매 반복마다 리스트에서 최소값 선택