[바미] 동전 0

문제

https://www.acmicpc.net/problem/11047

 

 

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const [N, K] = input[0].split(' ').map(Number);
const coinValues = input.slice(1).map(Number).reverse(); // 역순으로 배열을 한 번에 뒤집음

function minCoins(N, K, coinValues) {
    let remainingAmount = K;
    let coinCount = 0;

    // 동전을 큰 값부터 사용하면서, 나눗셈과 나머지 연산으로 동전 개수와 남은 금액을 동시에 계산
    for (let i = 0; i < N; i++) {
        const coinValue = coinValues[i];
        if (coinValue <= remainingAmount) {
            coinCount += Math.floor(remainingAmount / coinValue);
            remainingAmount %= coinValue;
        }
    }

    return coinCount;
}

const result = minCoins(N, K, coinValues);
console.log(result);

문제 해설

주어진 금액 𝐾를 최소한의 동전 개수로 만들어야 합니다. 사용할 수 있는 동전의 종류는 
𝑁개이며, 각 동전의 가치는 오름차순으로 주어지는 형태죠.

 

이 문제의 핵심은 '큰 동전부터 사용하여 남은 금액을 줄인다.'는 그리디 접근법입니다.

문제에서 주어진 동전들이 배수 관계이기 때문에 성립할 수 있죠.  동전을 큰 값부터 사용하기 위해, 동전 목록을 역순으로 정렬 해준 뒤, 현재 남은 금액에서 가장 큰 동전을 최대한 많이 사용한 후, 남은 금액에 대해 같은 과정을 반복하면 됩니다.

시간 복잡도

시간 복잡도는 알고리즘이 입력의 크기에 따라 얼마나 빠르게 실행되는지를 나타냅니다

 

배열을 역순으로 정렬하는 작업은 𝑂(𝑁)이 되고, 주어진 동전 목록을 한 번 순회하기 때문에 𝑂(𝑁)라는 시간 복잡도가 생깁니다.

따라서 전체 시간 복잡도는 𝑂(𝑁)이 됩니다.

공간 복잡도

공간 복잡도는 알고리즘이 얼마나 많은 메모리 공간을 사용하는지 나타냅니다.

 

입력 데이터를 저장하는 데  𝑂(𝑁)의 공간이 필요하고, 역순으로 정렬된 동전 목록 역시 𝑂(𝑁)공간을 사용합니다.

알고리즘 자체는 추가적인 메모리를 거의 사용하지 않으므로 전체 공간 복잡도는 𝑂(𝑁)이 됩니다.