반응형
최적해를 구하는 데에 사용되는 근사적인 방법, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해나가는 방식이다.
하지만 선택들을 계속 수집해서 최종적인 해답을 얻었을 경우 이 해답이 최적의 답이라는 보장은 없다.
적용이 잘되는 경우
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)); // 가격
}
}
반응형
'Java > Algorithm' 카테고리의 다른 글
[Java-Algorithm] 조합 Combination 알고리즘 (0) | 2021.05.25 |
---|---|
[Java-Algorithm] 백준 4307 개미 -그리디 알고리즘 (0) | 2021.05.24 |
[Java-Algorithm] Programmers 다리를 지나는 트럭 풀이 (0) | 2021.04.28 |
[Java-Algorithm] BFS 넓이 우선탐색 알고리즘이란? 인접리스트 (0) | 2021.04.26 |
[Java-Algorithm] DFS 깊이 우선탐색 알고리즘이란? 인접리스트 그래프 (0) | 2021.04.21 |