희렌버핏
[백준] 11047 동전 - JAVA 본문
문제
준규가 가지고 있는 동전은 총 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.
내 코드(236ms)
- 큰 화폐단위부터 나누면서 개수를 센다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int K = sc.nextInt();
int[] coin = new int[N];
for(int i=0; i<N; i++) {
coin[i] = sc.nextInt();
}
int count = 0;
int remain = K;
for(int i=N-1; i>=0; i--) {
if(coin[i] <= K) {
count += remain/coin[i];
remain = remain%coin[i];
}
}
System.out.println(count);
}
}
다른 사람 코드 (128ms)
- BufferedReader를 사용해서 속도를 높임
- remain을 안쓰고 K에 바로 값을 대입해서 사용했다.
- 나머지가 0일 때 나가게 하면 더 빨리 for문을 나갈 수 있다.
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[] coin = new int[N];
for(int i=0; i<N; i++){
coin[i] = Integer.parseInt(br.readLine());
}
int answer = 0;
for(int i=N-1; i>=0; i--){
if(K/coin[i] == 0)
continue;
answer += K/coin[i];
K %=coin[i];
if(K == 0)
break;
}
System.out.println(answer);
}
}
'Web > 알고리즘' 카테고리의 다른 글
[백준] 11399 ATM - JAVA (0) | 2020.11.24 |
---|---|
[백준] 1931 회의실 배정 - JAVA (0) | 2020.11.24 |
[백준] 2839 설탕 배달 - JAVA (0) | 2020.11.23 |
그리디 알고리즘 (0) | 2020.11.19 |
[프로그래머스/자바스크립트] 기능개발 / 스택큐 Level2 (0) | 2020.09.22 |