문제
준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.
출력
첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.
예제 입력 1
10 4200
1
5
10
50
100
500
1000
5000
10000
50000
예제 출력 1
6
예제 입력 2
10 4790
1
5
10
50
100
500
1000
5000
10000
50000
예제 출력 1
12
- 코드 -
import java.util.*;
public class Main {
public static void main(String[] args)
{
int N=0, K=0;
int i, tmp, count=0;
Scanner sc = new Scanner(System.in);
N = sc.nextInt(); // N값 입력받는다.
K = sc.nextInt();
if ((N<1 || N> 10) || (K<1 || K > 100000000))
{
// N의 범위를 올바르게 입력하지 않았을 경우
System.exit(1);
}
int[] arr = new int[N];
for(i=0; i<N; i++)
arr[i] = sc.nextInt();
tmp = arr.length - 1;
while(tmp >= 0)
{
if (K >= arr[tmp])
{
count += K/arr[tmp];
K = K % arr[tmp];
}
else
{
tmp -=1;
if (tmp == -1)
break;
}
}
System.out.println(count);
sc.close();
}
}
처음에 코딩부를 어떻게 짤지를 잘 생각하는 게 중요한 것 같다.