11047) 동전 0

문제요약

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

풀이

대충 수학 나눗셈 계산

코드

//
//  11047.cpp
//  algorithm_study
//
//  Created by Jihyun Kyoung on 2023/08/05
//
#include<iostream>

int main(){
    int n, k, num=0;
    scanf("%d", &n);
    scanf("%d", &k);

    int *arr = new int[n];
    for(int i=0;i<n;i++){
        std::cin>>arr[i];
    }
    for(int i=(n-1);i>-1;i--){
        if(k>=arr[i]){
            ////solve1
            // while(k>=arr[i]){
            //     k= k- arr[i];
            //     num++;
            // }
            //solve2
            num+=(k/arr[i]);
            k=k%arr[i];
        }
    }
    delete[] arr;

    std::cout<<num;
}