문제 풀이
문제 탐색하기
거스름돈 동전의 최소로 거슬러주기 위해서는 거슬러 줄 수 있는 동전의 액수 중 제일 큰 액수의 동전을 많이 줄 수록 최소의 개수로 돈을 거슬러 줄 수 있습니다.
이 문제에서는 2원과 5원으로만 돈을 거슬러 줄 수 있으며 최소로 줄 수 있는 동전의 개수를 구하는 문제입니다. 따라서 최대로 거슬러 줄 수 있는 5원의 개수를 먼저 측정하고 거스름돈의 액수와 딱 맞아 떨어지지 않으면 5원의 개수를 하나씩 줄이면서 2원의 개수를 구해가면 되는 문제입니다.
이 문제는 매순간 최적의 선택을 해서 해답에 도달할 수 있는 그리디 알고리즘을 바탕으로 해결책을 생각할 수 있었습니다.
Greedy Algorithm(탐욕 알고리즘)이란?
그리디 알고리즘은 최적의 해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 선택을 해야할 때 그 순간에 최적이라고 판단되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘 방법입니다. 즉, "현재 상황에서 지금 당장 좋은 것만 고르는 방법"으로 문제를 해결하는 방법입니다.
순간마다 하는 선택은 그 순간에 대해서는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없습니다. 하지만 그리디 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들입니다.
그리디 알고리즘 주요 속성
문제를 풀 때 아래의 두 조건이 성립해야 그리디 알고리즘을 활용하여 문제를 풀 수 있습니다.
- 탐욕 선택 속성(Greedy Choice Property) : 각 단계에서 '최선의 선택'을 했을 때 전체 문제에 대한 최적해를 구할 수있는 경우
- 최적 부분 구조(Optimal Substructure) : 전체 문제의 최적해가 '부분 문제의 최적해로 구성'될 수 있는 경우. 즉, 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 후 이를 조합하여 전체 문제의 최적해를 구하는 것을 의미합니다.
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int fiveCnt = n/5;
int twoCnt = (n-5*fiveCnt)/2;
int cash = 5*fiveCnt+2*twoCnt;
boolean returnOk = true;
while(cash != n){
if(fiveCnt==0){
returnOk = false;
break;
}
fiveCnt--;
twoCnt = (n-5*fiveCnt)/2;
cash = 5*fiveCnt+2*twoCnt;
}
System.out.println(returnOk == true ? fiveCnt+twoCnt : -1);
}
}
오늘의 회고
어제 문제에 이어서 그리디 알고리즘을 활용하여 문제를 풀었습니다. 그리디 알고리즘 개념에 대해 다시한번 찾아 볼 수 있는 좋은 기회가 되었고, 처음 코딩테스트를 접하게 되었을 때 들었던 거스름돈 문제를 풀 수 있어서 감회가 새로웠습니다ㅎㅎ