거스름돈(dp)

문제이해
n원을 만들려고 할때 money로 만들수 있는 방법의 수 구하기

dp(동적계획법)

1. dp[i]는 i원을 만드는 방법의 수

def solution(n, money):
    # dp 배열 초기화, 0부터 n까지 저장
    dp = [0] * (n + 1)
    dp[0] = 1  # 0원을 만드는 방법은 1가지

    # 각 동전에 대해서
    for coin in money:
        # dp 배열을 업데이트
        for i in range(coin, n + 1):
            dp[i] += dp[i - coin]

    return dp[n]


# 예제 입력
n = 5
money = [1, 2, 5]
print(solution(n, money))  # 출력: 4

 

 

<거스름돈 주기>

amount = 123 # 거스름돈
m = [1,10,50,100] # 화폐 단위

사용할 화폐를 최소화해서 -> 화폐단위를 내림차순
거스름돈 거슬러주기
사용할 화폐를 담은 리스트 반환


def solution(amount):
	m = [1,10,50,100]
    m.sort(reverse=True) # 내림차순하기
    change = [] # 사용한 화폐담는 리스트 (답이될 리스트)
    
    for coin in change:
    	if amount >= coin:
        	change.append(coin)
            amount -= coin
 	return change

 

 

<예산>

 

1. 가치같은 개념이 없음 그냥 최대한 많은 부서에 예산을 나눠주기

2. 예산리스트를 오름차순해서 하나씩 세기

 

 

def solution(d,budget):
	d.sort()
    answer = 0
    
    for i in d:
    	if i > budget:  # 오름차순이므로 예산보다 크면 뒤에는 볼필요 없음
        	break
       	budget -= i
        answer += 1
        
	return answer
    




d = [2,2,3,3]
budget = 10
print(solution(d,budget))