[알고리즘] JS 그리디 문제

그리디(탐욕법)

핵심 (추가 정리 필요)

• 당장의 최선의 선택 1개를 고르는 형식.

문제1. 거스름돈

첫째 줄에 N과 K(거슬러 줄 금액)
둘째 줄부터 N개의 줄에 동전의 가치가 주어짐.

K원을 만드는 데 필요한 동전 개수 구하기.

let input = [["10 4820"], "1", "5", "10", "50","100","500","1000","5000","10000","50000"]

// let a = input[0], a[0]은 n개 줄. a[1]은 k원.
// input[1]을 내림차순으로 정렬하고 k원을 나눠서 나머지 0을 만든다

const firstInput = input[0].toString().split(" ").map(Number)

let n = firstInput[0] // 10
let k = firstInput[1] // 4200

const secondInput = [];

for(let i=1; i<=n; i++) {
    secondInput.push(input[i])
    // @ts-ignore
    secondInput.sort((a,b) => b-a)
}

const moneyArr = secondInput.map(Number)
// 숫자로 변환

let cnt = 0;
// 거스름돈 동전 개수를 저장할 변수

for(let i=0; i<=n; i++) {
    if (k >= moneyArr[i])
    cnt += parseInt(k / moneyArr[i]) // 몫 구하기
    k %= moneyArr[i]
}

// 각 동전의 가치(moneyArr[i])가 현재 남은 돈(k)보다 작거나 같은 경우
// 해당 동전을 최대한 많이 사용하기 위해 몫(parseInt(k / moneyArr[i]))을 구하고
// cnt에 더하기. 그리고 나머지(k % moneyArr[i])를 다시 k에 저장하여 다음 동전 계산에 사용한다.

console.log(cnt) // 10

문제2. 최소 개수 구하기

5kg, 3kg 단위의 배달을 해야함.
최소로 배달할 수 있는 개수 구하기

let n = 22 // 22kg
let cnt = 0 // 개수 더하기
let flag = false // 조건에 안맞으면 -1 반환하기

while (n>=0) {
  // n이 주어지면 일단 5로 나눈 몫이 0으로 딱 떨어지는지 확인
    if(n==0 || n%5 == 0) {
        cnt += parseInt(n / 5)
        console.log(cnt)
        flag = true;
        break
    }
  // 5로 나눠서 딱 떨어지는게 아니면 3kg씩 뺀다.
    n -= 3
    cnt += 1;
  // 3kg 배달 1개 증가.
}
if(!flag) {
    console.log(-1)
}

문제3. N의 최대값 구하기

주어진 조건을 만족하는 N의 최대값을 찾는 것
조건은 서로 다른 숫자의 합이 N

let n = 200;
let sum = 0;
let current = 0;

//sum 누적 합이 n 이하일 때 까지 반복, current로 1부터!
while (sum <= n) {
    current += 1;
    sum += current
}

//sum이 n보다 커짐. sum이 n을 초과하는 순간의 값이 N의 최대값
console.log(current-1)