[Greedy] 엘리스 - 구슬 꾸러미(py)

문제

엘리스 토끼는 구슬 장사를 위해 구슬을 꾸러미에 담아 포장을 하고 있습니다. 엘리스 토끼가 준비한 구슬은 색상별로 무게가 모두 다르며 구슬 꾸러미 또한 구슬을 담아낼 수 있는 무게가 모두 달라 최소한의 구슬 개수를 활용해 꾸러미를 채우려고 합니다.

색깔과 무게가 다른 3가지 종류의 구슬이 무제한으로 주어집니다.

 

구슬	무게
빨간 구슬	250g
파란 구슬	40g
흰 구슬	10g

예를 들어 300g의 꾸러미를 만들기 위해서는 빨간 구슬 1개, 파란 구슬 1개, 흰 구슬 1개로 최소 3개의 구슬이 필요합니다.

지시사항을 참고하여 코드를 작성하세요.

 

지시사항

• 사용자로부터 구슬 꾸러미의 무게를 입력받고 꾸러미를 만드는 데 사용되는 최소 구슬의 수를 출력하세요.
  • (1 ≤ 구슬 꾸러미 무게 ≤ 10,000)
• 만약 무게에 맞추어 꾸러미를 만들 수 없는 경우에는 -1을 출력하세요.

 

입출력 예시

입력 예시	출력 예시
300	3
550	4
65	-1

---

풀이

아이디어

• 거스름돈 문제와 같은 Greedy, 무게가 무거운 구슬부터 빼준다.

# 꾸러미의 무게
n = int(input())

# 구슬의 무게
red = 250
blue = 40
white = 10

# 최소 사용 구슬의 수
cnt = 0

while n >= white:
    if n >= red:
        n -= red
        cnt += 1
    elif n >= blue:
        n -= blue
        cnt += 1
    elif n >= white:
        n -= white
        cnt += 1

if n == 0:
    print(cnt)
else:
    print(-1)

처음에 while문 안에 if elif 조건문을 if if 로만 작성해 60점이 나왔다.

처음에 큰 수부터 빼주고 안되면 그 더 작은 수를 빼주는 방식이기 때문에 if elif로 작성해 100점.

 

---

 

출처: https://kdt.elice.io/courses/69662/lectures/584526/lecturepages/6708522/