방명록
- [백준 / 자바] 11047번 동전 0 - 그리디2024년 01월 10일 02시 07분 08초에 업로드 된 글입니다.작성자: 민발자728x90
https://www.acmicpc.net/problem/11047
11047번: 동전 0
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
www.acmicpc.net
문제
준규가 가지고 있는 동전은 총 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의 배수)
10 4200 // 동전종류N 가치합K 1 5 10 50 100 500 1000 5000 10000 50000
출력
첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.
6
풀이
동전 Ai는 Ai-1의 배수임으로 그리디 사용 가능
① 가장 큰 동전부터 차례대로 K보다 작거나 같은 동전이 나올 때까지 탐색
② K보다 작거나 같은 동전을 K로 나워 몫을 동전 개수에 더하고 나머지 값을 K에 갱신
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); // 동전 종류 int k = Integer.parseInt(st.nextToken()); // 목표 금액 // 동전 배열 저장 int[] arr = new int[n]; for(int i = 0; i < n; i++) { arr[i] = Integer.parseInt(br.readLine()); } int count = 0; for(int i = n-1; i >= 0; i--) { if(arr[i] <= k) { count += (k/arr[i]); k = (k%arr[i]); } } System.out.println(count); } }
728x90'기록 > 백준' 카테고리의 다른 글
[백준 / 자바] 2869번 달팽이는 올라가고 싶다 (0) 2024.01.23 [백준 / 자바] 1541번 잃어버린 괄호 - 그리디 (0) 2024.01.10 [백준 / 자바] 24313번 알고리즘 수업 - 점근적 표기 1 (1) 2023.12.29 [백준 / 자바] 10773번 제로 (1) 2023.12.28 [백준 / 자바 ] 2920번 음계 (1) 2023.12.28 다음글이 없습니다.이전글이 없습니다.댓글