처음부터 차근차근
그리디 알고리즘 본문
반응형
그리디 알고리즘
현재 상태에서 최선의 선택지를 고르는 알고리즘이다.
지금까지 공부했던 알고리즘 중 개인적으로 가장 쉬웠던 알고리즘이었다!
문제
https://www.acmicpc.net/problem/11047
동전을 최소로 사용해서 입력된 금액을 만드는 문제이다.
예제 입력1을 보면
10 4200 // 동전 총 개수, 만들어야하는 금액
1
5
10
50
100
500
1000
5000
10000
50000
첫 번째 줄에 동전의 총 개수가 나오고, 그 다음 만들어야하는 금액이 나온다.
그 밑의 줄은 모두 동전들이다.
내 풀이
최소의 동전을 사용해서 금액을 만드려면 큰 값의 동전을 최대한 많이 써야한다.
큰 값 동전부터 시작해서 금액과 동전을 나눠 나온 값 만큼 동전을 쓰고, 다음 동전을 사용하는 방법으로 문제를 풀었다.
import java.io.*;
import java.util.*;
public class Main
{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int num = Integer.parseInt(st.nextToken());
int price = Integer.parseInt(st.nextToken());
int[] coins = new int[num];
int count = 0, gop = 0;
for (int i = 0; i < num; i++) {
coins[i] = Integer.parseInt(br.readLine());
}
for (int i = num-1; i >= 0; i--) {
if (coins[i] <= price && price != 0) {
gop = price / coins[i];
price -= coins[i] * gop;
count += gop;
}
else if (price == 0) {
break;
}
}
bw.write(String.valueOf(count));
bw.flush();
br.close();
bw.close();
}
}
반응형
'알고리즘' 카테고리의 다른 글
최소로 거치는 벌집 개수 구하기 (0) | 2022.10.22 |
---|---|
이친수 구하기 - 동적계획법 (2) | 2022.10.14 |
DFS, BFS 알고리즘 (0) | 2022.10.10 |
좋은 수 구하기 (2) | 2022.10.09 |
구간 합 구하기 (0) | 2022.10.07 |
Comments