[Beakjoon] 백준 16237번 Python

Beakjoon 16237, 이삿짐센터
solved.ac Silver4
Greedy 알고리즘

문제

알렉스는 이삿짐센터를 운영하고 있다. 오늘 이사해야 하는 집에는 무게가 1kg인 물건이 A개, 2kg인 물건이 B개, 3kg인 물건이 C개, 4kg인 물건이 D개, 5kg인 물건이 E개 있다.

물건을 운반하려면 바구니에 물건을 담아야 하는데, 바구니에는 최대 5kg까지 물건을 담을 수 있다. 알렉스는 모든 물건을 담는데 필요한 바구니 개수를 최소로 하려고 한다.

가방 하나에 담은 물건 무게의 합은 5kg을 넘을 수 없다.

물건의 무게가 주어졌을 때, 모든 물건을 담는데 필요한 바구니 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C, D, E가 주어진다. (0 ≤ A, B, C, D, E ≤ 1,000)

출력

첫째 줄에 모든 물건을 담는데 필요한 바구니 개수의 최솟값을 출력한다.

Solution

A,B,C,D,E = map(int, input().split())

count = E + D
A -= D

while C > 0:
    count += 1
    if B > 0:
        B -= 1
        C -= 1
    elif A > 0:
        A -= 2
        C -= 1
    else:
        C -= 1


while B > 0:
    count += 1
    if B > 1 and A > 0:
        B -= 2
        A -= 1
    elif B > 0 and A > 0:
        B -= 1
        A -= 3
    else:
        B -= 2

while A > 0:
    count += 1
    A -= 5

print(count)

풀이

먼저 E와 D를 모두 박스에 담습니다. 그러곤 D의 개수만큼 A를 빼줍니다. ( 4 + 1 )

그다음 C를 박스에 담아줍니다. C를 박스에 다 담을 때까지 B와 A를 같이 담아줍니다. ( 3 + 2, 3 + 1 + 1 )
그다음 B를 박스에 담아줍니다. B를 박스에 다 담을 때까지 A를 같이 담아줍니다.( 2 + 2 + 1 , 2 + 1 + 1 + 1 )

나머지 A를 5개씩 박스에 담아줍니다.

 

---

16237번: 이삿짐센터