코딩테스트 - Greedy

개념

때로는 당장 눈앞의 최선이, 최고의 결과를 가져온다

• 현재 차례의 최고의 답을 찾는 문제

• 어려운 이유 : 왜 그런지 증명하기가 어려움

• 예시 : 다른 금액의 동전이 여러개 주어졌을때 M원을 만드는 최소의 개수

• 아이디어

  • 큰 금액의 동전부터 차감
  • 반례? : 동전의 개수가 무한대라서 없는것으로 보임
  • K를 동전 금액으로 나눈뒤 남은값으로 갱신

• 시간복잡도
  O(N)

• 자료구조

  • 동전 금액 : int[]
  • 동전 사용 cnt : int
  • 남은 금액 : int

문제 : 11047

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

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.
ex)
input:
10 4200
1
5
10
50
100
500
1000
5000
10000
50000

output:
6

// Greedy

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];

rl.on("line", function (line) {
  input.push(line);
}).on("close", () => {
  /*
1. 아이디어
    - 오름차순이므로 거꾸로 순회하기 위해 역정렬
    - 동전 for >
        - 동전 사용개수 추가
        - 동전 사용한 개수만큼 k값 갱신

2. 시간복잡도
    - O(n)
3. 자료구조
    - 동전 금액 : int[]
    - 동전 사용 cnt : int
    - 남은 금액 : int
    */

  let [N, K] = input[0].split(" ").map(Number);
  const coins = [];
  for (let i = 1; i <= N; ++i) {
    coins.push(parseInt(input[i]));
  }
  let cnt = 0;

  //역정렬
  coins.reverse();

  for (let i = 0; i < coins.length; ++i) {
    //동전 사용개수 추가
    cnt += Math.floor(K / coins[i]);
    //동전 사용한 개수만큼 k값 갱신
    K = K % coins[i];
  }

  console.log(cnt);
});

알아야할것

• 실전 문제에서, 그리디로 푸는 문제임을 생각하기 어려움
• 그리디 사용 이유 설명 or 반례 찾기 연습이 필요함