백준 11047 C++

https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

생각

1. 이건 knapsack 문제다! 동전이니까 자르지 못하는 knapsack 문제

2. 근데 그렇게 어려운 고민 할 필요 없이 단순하게 금방 풀 수 있는 문제다! 알고리즘 구상하지 않고 빠르게 풀 수 있음

 

정답 코드

#include <iostream>
using namespace std;

int main(){
    int n,k;
    cin >> n >> k;
    int arr[n];
    
    for(int i=n-1 ; i>=0 ; i--){ 
    // 입력이 오름차순이니까 반복문을 거꾸로 받아서 내림차순 배열이 되게 하기
    // 밑에 반복문에서 바꾸든 sort로 재배열 하든 상관 없음! 다 똑같다
        cin >> arr[i];
    }
    
    int count = 0;
    for(int i=0; i<n ; i++){
        if(arr[i] <= k){ // 최대가치 k보다 처음으로 작은 값부터 시작해야되니까!
            count += k / arr[i]; // k / arr[i]를 하면 i번째 인덱스로 채울 수 있는 최대 횟수!가 나옴
            k = k % arr[i]; // 채우고 남은 값(가치)!
        }
    }
    cout << count << endl;
}