Java/Algorithm

[Java-Algorithm] 백준 5585 거스름돈 -그리디 알고리즘

Jeong Jeon
반응형

최적해를 구하는 데에 사용되는 근사적인 방법, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해나가는 방식이다.
하지만 선택들을 계속 수집해서 최종적인 해답을 얻었을 경우 이 해답이 최적의 답이라는 보장은 없다. 

 

적용이 잘되는 경우

1. Greedy Choice Property (탐욕 선택 조건)

  • 앞의 선택이 이후 선택에 영향을 주지 않는 경우. 즉, 각 사건들이 서로 독립적일 때 잘 맞는다. 

2. Optimal Substructure (최적 부분 구조 조건)

  • 문제에 대한 최적해가 부분 문제에 대해서도 최적인 경우

 

이문제는 쉬운 문제다 그리디가 뭐지? 하는 나도 풀었던 문제 정리..

 

문제 : https://www.acmicpc.net/problem/5585

 

5585번: 거스름돈

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사

www.acmicpc.net

 

해결 :

public class greedyAlgorithm {

	public static int price;
    public static int count;
    public static int[] coinArr = {500, 100, 50, 10, 5, 1}; //코인 종류
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        price = 1000 - sc.nextInt(); //잔돈= 1000-지불할 금액
 
        //동전이 큰순서대로 정렬되있기 때문에 큰순서대로 동전을 빼서 지불한다.
        for(int coin:coinArr) {
            getCount(coin);
        }
        
        System.out.println(count);
    }
    
    public static void getCount(int coin) {
        count += (price / coin); //지불할 금액 / 동전금액 = 동전 갯수
        price = price - (coin * (price / coin)); // 가격
    }
}
반응형