[이것이 코딩 테스트다 with Java] 그리디 예제 - 만들 수 없는 금액

만들 수 없는 금액

난이도 ●○○ | 풀이 시간 30분 | 시간 제한 1초 | 메모리 제한 128MB | 기출 K 대회 기출

동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.
예를 들어, N=5 이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리(화폐 단위) 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원입니다.
또 다른 예시로, N=3이고, 각 동전이 각각 3원, 5원, 7원 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 1원입니다.

 

입력 조건

• 첫 째줄에는 동전의 개수를 나타내는 양의 정수 N이 주어집니다. (1≤N≤1,000)
• 둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분합니다. 이때, 각 화폐 단위는 1,000,000 이하의 자연수입니다.

출력 조건

• 첫째 줄에 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력합니다.

입력/출력 예시

입력 예시	출력 예시
5 3 2 1 1 9	8

요점

• 동전의 화폐를 오름차순으로 정렬한다. 
• 맨 처음 동전부터 차례대로 동전을 추가해가며 만들 수 없는 금액을 찾는 방식으로 풀이한다.

소스 코드

import java.util.*;

public class Main
{
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int n = scan.nextInt();
		int coins[] = new int[n];
		int result = 1;
		
		for(int i = 0; i < n; i++){
			coins[i] = scan.nextInt(); 
		}
		
		Arrays.sort(coins);
		
		for(int i = 0; i < n; i++){
			if(result < coins[i]) break;
			result += coins[i];
		}
		
		System.out.println("result = " + result);
	}
}

 

문제 풀이 후기

풀었지만 아직도 잘 이해가 안 되는 문제다. 그리디 알고리즘에서 많이 나오는 문제 중에  이전 계산은 현재에도 포함되어 있다는 식의 문제가 잘 이해되지 않는다. 얼마나 더 문제를 풀어봐야 이해할 수 있을지 척하면 척 나올 때까지 열심히 풀어보는 수밖에 없지 않을까 싶다.

 

GitHub: https://github.com/Leeyeonjae/coding-test/blob/main/11_Greedy_Example/11_4_impossibleAmount.java

참고서적 : 이것이 취업을 위한 코딩 테스트다 with 파이썬 by 나동빈