[이코테 with Java] 거스름돈 문제 (그리디 알고리즘)
2024. 1. 18. 11:29ㆍ알고리즘
1. 내가 푼 방식
// 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전히 무한히 존재한다.
// 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라.
// 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int coin = scanner.nextInt();
int[] coinArray = {500, 100, 50, 10};
int sum = 0;
for(int i=0; i<coinArray.length; i++){
if( i > 0 ){
sum += coin % coinArray[i-1] / coinArray[i];
}
else if( i == 0 || i == coinArray.length - 1 ){
sum += coin / coinArray[i];
}
}
System.out.print(sum);
}
}
2. 동빈님이 푼 방식
// 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전히 무한히 존재한다.
// 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라.
// 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.
import java.util.*;
public class Main{
public static void main(String[] args){
int n = 1260;
int cnt = 0;
int[] coinTypes = {500, 100, 50, 10};
for (int i = 0; i < 4 ; i++){
int coin = coinTypes[i]; // coin이라는 변수에 동전 단위를 넣음
cnt += n / coin; // 해당 동전 단위의 갯수를 더해줌(몫)
n %= coin; // 해당 동전 단위로 나눈 나머지를 n에 넣어줌
// 이렇게 하면 그 다음 인덱스에는 그 나머지를 다시 동전 단위로 나누어 몫을 구해줄 수 있음
// 예를 들어, 500원으로 나누면 2인데, 그 나머지인 260원을 다시 100원으로 나눠줘야 함
}
System.out.println(cnt);
}
}
나는 처음 입력을 받을 때나, 마지막 입력을 받을 때는 나머지를 구할 필요가 없으므로,
그 외의 경우에만 몫과 나머지 모두를 구하게 했다.
동빈님은 몫을 구한 다음, 나머지를 구한 값을 n에 넣어주고, 그 다음에는 자동으로 그 나머지 값에 대한 몫을 구하도록 했다. 예를 들어, 1260원을 500원으로 나누면 2이고, 그 나머지인 260을 100원으로 나눠줘야 하기 때문이다.
나는 조건문을 한 번 더 거쳐야 하지만, 동빈님 코드에서는 거칠 필요 없이 바로 연산을 수행하여 효율적이다.
'알고리즘' 카테고리의 다른 글
[이코테 with Java] 숫자 카드 게임(그리디 알고리즘) (0) | 2024.01.18 |
---|---|
[이코테 with Java] 큰수의 법칙(그리디 알고리즘) (0) | 2024.01.18 |
[백준] 2908번(StringBuilder 활용 X, StringBuilder 활용 O) (0) | 2024.01.16 |
[백준] 3052, 10811 (0) | 2024.01.12 |
[백준] 10810번 문제 해결 (2) | 2024.01.10 |