BOJ-11047

by

11047호: 코인 0

N과 K는 첫 번째 줄에 표시됩니다.

(1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 두 번째 행부터 오름차순으로 N행에 주화의 값 Ai를 부여한다.

(만약 1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2, Ai는 Ai-1의 배수)

www.acmicpc.net

'추천 관련글,

문제 설명

  • 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';
}