-
백준 11047번 그리디 알고리즘알고리즘 자료구조 2021. 12. 4. 06:31728x90
문제 설명
N종류의 동전으로 K를 만들라고 합니다.
근데 K를 만들 때 필요한 동전의 개수의 최솟값을 구하라고 하죠
K = 5500원
N = 10 50 500 1000
이라고 한다면 1000원 5개로 오천 원을 만들고
500원 한 개로 5500원을 만들 수 있죠
여기서 쓴 동전의 개수는 6개
이런 식으로 구하라는 거예요
case , money = map(int , input().split(' ')) #case는 동전의 종류 money는 우리가 만들어야할 돈 coin = [] #동전들을 담을 배열 temp = count = 0 for i in range(case): user_coin = int(input()) coin.append(user_coin) for m in reversed(coin): #입력은 오름차순으로 입력된다했죠 근데 최소값을 구하라고하니까 뒤집어서 큰 동전부터 검사합니다 temp = money//m #만약에 돈이 5300원이고 동전이 2000원이면 2번 뽑아줄수있죠 count += temp #동전으로 돈을 나눈 몫을 count에 담아줍니다 money %= m #돈을 뽑을수있는대로 뽑아줬으면 돈을 동전으로 나눈 나머지로 치환해줍니다 print(count)
728x90'알고리즘 자료구조' 카테고리의 다른 글
백준 5622번 다이얼 Python (0) 2021.12.07 백준 11399번 (0) 2021.12.05 백준 1931번 회의실 (0) 2021.12.04 백준 17413번 파이썬 (0) 2021.09.17 백준 4673번 셀프넘버 Python (0) 2021.09.15