[Node.js] 11047번 : 동전 0

---

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

---

풀이 과정

실수로 완전탐색 방식으로 풀어버릴 뻔 했다….
처음 풀어보는 그리디 알고리즘 유형이었어서 여러 풀이법들을 참고했다.

1. 그리디 알고리즘…?
   • 그리디 알고리즘은 모든 경우의 수를 탐색하는 알고리즘이 아니다.
   • 따라서 경우에 따라 내가 도출한 답이 최적의 답이 아닐 수도 있다. ( 하지만 빠를 수는 있음 )
2. 코드 로직
   • 우선 N값과 K값을 선언해준다.
   • 카운트를 세야 하기 때문에 count 변수 또한 선언해준다.
   • 그리디 알고리즘이기 때문에, 작은 값에서 큰 값으로 탐색하는 것은 비효율적이다.
     • 따라서, 배열의 가장 우측에서부터 차례대로 탐색하는 것이 빠른 해답을 찾기 위한 방법일 것이다.
     • for문 또한 i가 감소하는 식으로 구성한다.
   • 우측에서부터 진행되기 때문에 최소 조합을 구성하기 위해선 K/Arr[i]가 count에 담기면 된다.
   • 그리고 K값은 해당 Arr[i]값으로 나눈 나머지, 즉 K%= Arr[i]가 되면 된다.
   • 이렇게 반복문을 계속 돌리면 우측에서부터 탐색했을 경우의 최소 동전 집합의 개수를 구할 수 있다.

---

소스 코드

function coin(arr, NK) {
  // K와 N 선언
  const N = NK[0];
  let K = NK[1];
  let count = 0;
  // 합이 K가 되는 동전 조합의 최소값 구하기
  for (let i = N - 1; i > 0; i--) {
    count += Math.floor(K / arr[i]);
    K %= arr[i];
  }
  return count;
}

---