백준 (11047) - 동전0

 

그리디 알고리즘은 탐욕 알고리즘이라고도 불리우며 쉽게 설명하면

매 선택마다 최선의 선택만을 하는 것이다.

이것이 항상 최선의 값을 찾는다는 보장은 없지만 빠른 시간안에 그 근사값을 찾는다는 것에 의의가 있다.

보통 그리디 알고리즘을 설명할 때 거스롬든을 예로 든다. 

6480원을 

5000원 ,1000원, 100원, 50원, 10원으로 가장 최소의 지폐 및 동전만 사용한다고 가정한다면,

 

가장 큰 가치의 화폐를 먼저 사용하면서 거스름돈에 대한 값을 줄여나가면 가장 최적의 해를 찾을 수 있을 것이다.

 

이때 중요한건 화폐가 일정한 배수로 증가 또는 감소한다는 것을 주목해야하는데, 

배수가 있어야 그리디 알고리즘으로 해결할 수 있다고 생각하면 된다

 

11047 문제

위 문제에서도 1, 5, 10, 50, 100 , 500 .... 50,000으로 5배, 2배, 5배 2배 .. 로 반복하면서 값이 증가하는 동전이 주어졌다

 

따라서 그리디 알고리즘으로 해결한다

 

먼저, 아래와 같이 동전의 값을 입력받고, 배열에 저장한 후 reverse 함수를 사용하여 뒤집고 가장 큰 가치의 동전부터 계산한다.

for(let i = 1; i <= n; i++)
{
    arr.push(input[i].split('\n').map(Number));
}
arr.reverse();

 

그다음 반복문을 통해 값을 계산한다

이때 화폐통해 계산할 때 는 k보다는 작고 남은 화폐중에 가장 큰 화폐를 사용해야 최적의 해를 구할 수 있다.

for(let i = 0; i < n; i++)
{
    let length = 0;
    if(k >= arr[i]) // 가장 큰 화폐를 찾는 과정
    {
        cnt += parseInt(k / arr[i]);
        length = Math.pow(10,String(arr[i][0]).length-1);
        k -= parseInt(k /= arr[i]) * arr[i];
    }
}

 

이때 예를들어 4200원이라면,

arr[i]가 1000일 때 if문이 true가 되고

4200 / 1000 한 값인 4가 cnt에 저장되고,

k값에서 4 * 1000을 빼서 나머지 거스름돈을 저장하게 하였다