99클럽 코테 스터디 9일차 TIL - 저울 (그리디)

문제: https://www.acmicpc.net/problem/2437
알고리즘 분류: 그리디 알고리즘, 정렬

문제 파악

그리디 알고리즘을 활용해 풀 수 있는 문제
주어진 저울추로 측정할 수 없는 가장 작은 양의 정수를 찾아야 함

문제 접근

저울추를 오름차순으로 정렬한 뒤, 현재까지 만들 수 있는 최대 무게를 계속 추적

1. 저울추를 오름차순으로 정렬

2. 변수 target을 1로 초기화 → 현재까지 1부터 target-1까지의 모든 무게를 만들 수 있다

3. 각 저울추를 순회하며:
   만약 현재 저울추의 무게가 target보다 크다면, target이 만들 수 없는 최소 무게이므로 반복을 종료
   그렇지 않다면, 현재 저울추를 사용하여 target에 현재 저울추의 무게를 더함
   → 1부터 target + weightArr[i] - 1까지의 모든 무게를 만들 수 있음

4. 모든 저울추를 처리한 후, target은 만들 수 없는 최소 무게가 됩니다.

예제 입력값 3 1 6 2 7 30 1에 대해:

오름차순 정렬: [1, 1, 2, 3, 6, 7, 30]

초기 target = 1
첫 번째 추(1): target = 1 + 1 = 2 (1까지 만들 수 있음)
두 번째 추(1): target = 2 + 1 = 3 (2까지 만들 수 있음)
세 번째 추(2): target = 3 + 2 = 5 (4까지 만들 수 있음)
네 번째 추(3): target = 5 + 3 = 8 (7까지 만들 수 있음)
다섯 번째 추(6): target = 8 + 6 = 14 (13까지 만들 수 있음)
여섯 번째 추(7): target = 14 + 7 = 21 (20까지 만들 수 있음)
일곱 번째 추(30): target = 21 + 30 = 51 (50까지 만들 수 있음)

최종적으로 측정할 수 없는 가장 작은 양의 정수: 21

내 코드

const fs = require('fs');
const [n, weights] = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const weightArr = weights.split(' ').map(Number).sort((a, b) => a - b);

let target = 1;

for (let i = 0; i < weightArr.length; i++) {
  // 현재 저울추의 무게가 target보다 크면, target이 만들 수 없는 최소 무게
  if (weightArr[i] > target) {
    break;
  }
  
  // 현재 저울추를 사용해 target을 업데이트
  // target + weightArr[i]까지의 모든 무게를 만들 수 있게 됨
  target += weightArr[i];
}

console.log(target);

그리디 알고리즘(Greedy Algorithm)

• 매 선택 단계에서 현재 상황에서 가장 최적인 선택(locally optimal choice)을 하는 알고리즘

• 예) 거스름돈 문제: 최소한의 동전 개수로 거스름돈을 만드는 문제

function coinChange(amount, coins) {
    // 큰 금액의 동전부터 사용하기 위해 내림차순 정렬
    coins.sort((a, b) => b - a);
    
    let totalCoins = 0;
    let remainingAmount = amount;
    let result = {};
    
    for (let coin of coins) {
        const count = Math.floor(remainingAmount / coin);
        if (count > 0) {
            result[coin] = count;
            totalCoins += count;
            remainingAmount -= coin * count;
        }
    }
    
    return {
        totalCoins: totalCoins,
        coinsUsed: result,
        remainingAmount: remainingAmount
    };
}

// 예시: 한국 화폐 단위로 4,760원을 거슬러주기
const koreanCoins = [5000, 1000, 500, 100, 50, 10];
console.log(coinChange(4760, koreanCoins));

참고
https://bedecked-operation-4d1.notion.site/99-9-TIL-1d1eb405261e80bfa59ec5cbd1da3343