Baekjoon11047: 동전 0

Baekjoon11047: 동전 0

동전 0

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초 256 MB 63302 33632 26262 52.513%

문제

준규가 가지고 있는 동전은 총 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

풀이

현재 K원에서 만들 수 있는 동전 중 최대가치인 것을 골라내고 다시 남은 돈에서 낼 수 있는 동전 가치 중 최대인 것을 고른다.

제한조건

동전의 가치는 배수로 나타나기 때문에 무조건 큰 단위의 동전을 내는 것이 유리하다. 300원 500원 이런식이 아닌 300원 600원과 같은 배수의 형태이기 때문이다.

반복문

현재 가지고 있는 돈 K보다는 작지만 동전 가치 중에서는 가장 큰 동전을 고르면 된다. 이를 위해 배열에 크기가 큰 동전 순으로 배치하고

K보다 작아질 때 바로 그 동전 가격으로 K를 나누어서 지불하고 나머지를 다시 K에 넣어 연산을 반복한다

import java.util.Scanner; import java.util.StringTokenizer; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(), K=sc.nextInt(); int[] coin = new int[N]; for(int i=N-1;i>=0;i--){ //크기가 큰 동전부터 배열에 배치한다 coin[i]=sc.nextInt(); } int sum=0; for(int i=0; i=coin[i]) { //동전의 크기가 현재 남은 돈 K보다 작아지는 순간 나눈다 sum+=K/coin[i]; //동전의 개수를 기록한다 K%=coin[i]; //나눈 나머지를 다시 k에 집어넣는다 } } System.out.println(sum); } }

from http://devyoseph.tistory.com/127 by ccl(A) rewrite - 2021-10-31 22:27:12