The gift(그리디 알고리즘)

www.codingame.com/training/medium/the-gift

Practice Greedy algorithms with the exercise "The Gift"

문제: 선물의 가격과 n인

의 소지금을 입력하면 가장 공평하게 지불할 수 있는 방법 찾기

 

경우의 수를 살펴보자

1)선물이 300원이고 3인 각자 120원씩 있다면 -> 모두 100원씩 지불한다

2)선물이 300원이고 3인이 각자 50원, 200원, 200원이 있다면 -> 50원, 125원, 125원씩 지불한다

3)선물이 300원이고 3인이 각자 200원, 100원, 50원씩 있다면 -> 150원, 100원, 50원씩 지불한다.

 

즉, 3인이 공평하게 낼 수 있다면 똑같이 지불하고, 아니면 가장 적은 사람이 최대값을 내고 남은 값을 다시 두 명이 나누어 지불하면 될 것이다.

 

import math

n = int(input())#몇명인가
c = int(input())#선물가격
budget = [] #예산들
sum_budget = 0 #예산들의 합

#각각의 예산
for i in range(n):
    value = int(input())
    budget.append(value)
    sum_budget  = sum_budget + value
    
#1. 선물을 살 수 있는지 확인
if sum_budget < c:
	print("Imposible")
#2. 선물을 공평하게 지불할 수 있는지 확인
else:
	remain = n
	sorted(budget)#가장 적은 사람부터 내기
	for x in range(n):
		fair_budget = c // remain #남은 사람들끼리 나누기
		if budget[x] > fair_budget:
			c = c - fair_budget #돈이 충분하면 지불하기
			print(fair_budget)
		else:
			c = c - budget[x] #돈이 부족하면 전부 지불하기
			print(budget[x])
		remain -= 1 #지불한 사람은 제외