BOJ-11047

문제 설명

• n: 코인 종류 수
• k: 양
• k와 일치하려면 몇 개의 n이 필요합니까?

문제 접근

• 큰 단위로 분해하기 시작할 수 있습니다.
  
  
  • 즉 4,600원 -> 1,000원 ​​* 4개 + 500원 * 1개 + 100원 * 1개
• 풀기 쉬운 문제인데 반례 때문에 시간이 오래 걸렸다.
  
  그 외에는 20분도 채 걸리지 않은 것 같습니다.
  
  
  • 반례. 1 1 1 입력 결과가 1이어야 하는데 결과가 0인 경우

// 20 min
#include <iostream>
using namespace std;

int main(void) {
  int n, k, cnt = 0;
  cin >> n >> k;

  int arr(n);
  // index를 0 ~ <n이 아니라 1 ~ <=n 으로 해야 정신건강에 이로움
  for (int i = 1; i <= n; i++)
    cin >> arr(i);

  // 큰 단위부터 계산해보자
  for (int i = n; i > 0; i--) {
    // i.e. 4600원 일때, mul_cnt = 4 (int형이니 4600 / 1000에서 600원은 버린다)
    int mul_cnt = k / arr(i);
    // 반례. 370 / 1000 은 mul_cnt가 0 이므로 계산할 필요가 없다
    if (mul_cnt > 0) {
      cnt += mul_cnt;
      k -= mul_cnt * arr(i);
      // 쪼개다가 쪼갤개 없으면 break
      if (k == 0)
        break;
    }
  }

  cout << cnt << '\n';
}