오늘은 이게 진짜 마지막이다 (중간 첫 시험 D-5)
acmicpc.net/problem/11047

Greedy algorithm

현재 상황에서 당장 최선인 선택을 하는 것을 의미한다.
전체로 봤을 때는 최선의 선택이 아닐 수 있다. (아닌 경우는 나중에 다른 문제를 풀면서 알아보도록 하자)

처음에 틀린 이유

while문을 쓰고 i--;를 하는 방식으로 구현했는데 i=0인 경우를 고려해주지 않았다.

Solution

#include <stdio.h>

int main() {
  int n, k, i;
  int ans = 0;
  int coin[11] = {};
  scanf("%d %d", &n, &k);
  for (i = 0; i < n; i++)
    scanf("%d", &coin[i]);
  i = n - 1;
  while (i >= 0 && k > 0) {
    ans += (k / coin[i]);
    k = k - (k / coin[i]) * coin[i];
    //printf("k:%d ans:%d i:%d\n", k,ans,i);
    i--;
  }
  printf("%d", ans);
}