백준알고리즘 11047번 동전 0 C#

세부 정보

• 사이트: 백준알고리즘
• 번호: 11047
• 문제명: 동전 0
• 언어: C#
• 분류: 그리디 알고리즘
• 비고: 

 

문제

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

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

 

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

풀이

동전의 가치를 입력할 때는 작은 순서대로 입력을 받지만 최소 개수를 구하기 위해서는 큰 것부터 계산해야 한다. 따라서 동전의 최소 개수를 구하는 for문에서는 coinValue.Length - 1부터 0까지 내려가는 방식으로 처리해야 한다.

StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

// 동전의 가치 종류와 동전 가치의 목표합 입력
int[] nk = sr.ReadLine().Split().Select(int.Parse).ToArray();
// 동전의 가치 종류를 저장할 배열
int[] coinValue = new int[nk[0]];
// 목표합 달성을 위한 최소 동전 개수
int minCoinCount = 0;

// 동전의 가치 입력
for(int i = 0; i < coinValue.Length; i++)
    coinValue[i] = Convert.ToInt32(sr.ReadLine());

for(int i = coinValue.Length - 1; i >= 0 ; i--)
{
    // 최소 동전 개수는 목표합에 동전의 가치를 나눠서 계산한다.
    minCoinCount += nk[1] / coinValue[i];
    // 목표합을 동전 가치로 나눈 나머지 값으로 차액을 반영한다.
    nk[1] %= coinValue[i];
}

// 최소 동전 개수 출력
sw.WriteLine(minCoinCount);

sr.Close();
sw.Close();

 

후기

문제를 풀어보기 전 지난 일이 생각나서 int.Parse()와 Convert.ToInt32의 차이도 조사해 보았다. 일반적으로 int.Parse가 더 빠르지만 그 차이는 미미하다. 그리고 입력 값이 항상 유효한 숫자 문자열임을 확신할 수 있을 때만 사용할 수 있다. 반면 Convert.ToInt32는 null 값을 처리할 수 있는 유연성이 있어서 더 안전한 스크립트 작성이 가능하다고 한다.

그리디 알고리즘에 익숙해 지려면 경우별로 어떻게 처리해야 할 지를 머릿속에 다 쌓아두어야 할 것 같았다. 한 경우를 알아두면 유사한 문제에서 더 빠르게 해결 방법을 떠올리는 것이 쉬워진다.