[백준] 12981번 공 포장하기 [Python] - 그리디

 

세가지 색깔의 공이 있고, 공을 담는 최소 박스 개수 구하는 문제

1 박스에 공은 1,2 또는 3개를 넣을 수 있습니다.

모두 같은 색으로 넣거나 모두 다른 색으로 넣어야 합니다.

 

문제

빨간 공 R개, 초록 공 G개, 파란 공 B개를 가지고 있다.

오늘은 이 공을 박스로 포장하려고 한다. 박스에는 공이 1개, 2개, 또는 3개 들어갈 수 있다.

박스에 들어가는 공의 색은 모두 다르거나, 모두 같아야 한다.

필요한 박스 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 R, G, B가 주어진다. $(1 ≤ R, G, B ≤ 100)$

출력

첫째 줄에 필요한 박스 개수의 최솟값을 출력한다.

12981번: 공 포장하기 $($acmicpc.net$)$

 

모두 같은 색으로 3개씩 $($3으로 나눈 몫$)$ 넣을 때 필요한 박스 수 구하기

나머지로는 0, 1, 2개가 가능하므로

한 색깔만 2개 남고 나머지는 0개 남는다면 1박스면 충분하고

나머지 경우에는 세가지 색 중에서 가장 많이 남은 색의 개수만큼 박스가 필요하다. 

import sys
li = map(int, sys.stdin.readline().split())
n, m = 0, []
for c in li:
    q, r = c//3, c%3
    n += q
    if r:
        m.append(r)
if len(m) == 1:
    n += 1
elif len(m) > 1:
    n+=max(m)
print(n)

 

예제 입력 1 

4 2 4

예제 출력 1 

4

예제 입력 2 

1 7 1

예제 출력 2 

3

예제 입력 3 

2 3 5

예제 출력 3 

4

예제 입력 4 

78 53 64

예제 출력 4 

66

예제 입력 5 

100 100 100

예제 출력 5 

100

힌트

첫 번째 예제는 RGB, RG, RR, BBB로 포장하면 된다.

두 번째 예제는 RGB, GGG, GGG로 포장한다.