ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 백준 11047번 그리디 알고리즘
    알고리즘 자료구조 2021. 12. 4. 06:31
    728x90

    링크

    문제 설명

    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
Designed by Tistory.