자바 토이프로젝트와 스터디 프로젝트를 핑계로 블로그와 알고리즘에 소홀해졌었는데 스터디에서 다시 하루에 한 개씩 주마다 주제를 정해서 같이 풀고 풀이과정 블로그에 올리기로 했다:)
이번주 남은 이틀과 다음주 주제는 그리디 알고리즘으로 정했다.
오늘 문제만 쉽고 낼부터는 어렵다던데 힝
그리디 알고리즘
탐욕 알고리즘 또는 욕심쟁이 알고리즘이라고도 불린다.
미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법으로 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘이다.
문제 링크
💻 문제
준규가 가지고 있는 동전은 총 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int coin=sc.nextInt();
int amount=sc.nextInt();
int count=0;
int A[]=new int[coin];//동전 종류
for(int i=0;i<coin;i++){
A[i]= sc.nextInt();
}
for(int i=coin-1;i>=0;i--){
if(A[i]<=amount){
if(amount<=0){
break;
}
count+=amount/A[i];
amount=amount%A[i];
}
}
System.out.println(count);
}💡 코드 설명
- 동전의 개수(coin)와 가격(amount)을 순서대로 입력받는다.
- 그리고 배열(A)에 동전종류를 입력받는다.(배열의 크기는 앞에서 봤던 동전 단위의 개수이다)
- 동전의 가치가 오름차순으로 입력된다고 했으니 배열에는 1 5 10 50 ... 이렇게 정렬되어 있다.
- 그리디 알고리즘은 그 상황에서 최선의 선택을 하는 알고리즘이니 가장 적게 동전개수를 만들어야 한다.
- 동전을 최대한 줄여야 하므로 배열 맨 끝부터 for문을 돌린다.
- 이때 가격보다 동전의 단위가 더 크면 안되니까
if(A[i]<=amount)문으로 가격보다 동전의 단위가 더 크지 않을때 연산을 한다 - count에는 동전의 개수를 저장한다.
count+=amount/A[i]; - amount에는 계산하고 남은 나머지를 저장해 가장 적은 동전 개수를 계산한다.
- 그리디 알고리즘을 활용할 수 있었던 이유: 동전들에 배수관계가 성립할때만 한정. 대부분의 화폐는 1,5,10,25,50 등 딱 떨어지는 수치를 가지고 있기 때문에 그리디로 해결된다.
:)