문제
동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하시오.
입력조건
출력조건
첫째 줄에 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력합니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class 만들수없는금액 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
String s[] = br.readLine().split(" ");
Integer coin[] = new Integer[N];
int target=1;
for (int i=0;i<N;i++) {
coin[i] = Integer.parseInt(s[i]);
}
Arrays.sort(coin);
for (int i=0;i<N;i++) {
if(target< coin[i]) break;
target+=coin[i];
}
System.out.println(target);
}
}
target
: 만들 수 있는 금액인지 확인하는 변수그리디 알고리즘을 이용하여 정렬된 배열의 앞에서부터 차례로 탐색을 한다. 이 때 현재까지의 합까지는 만들 수 있는 금액이다.
예를 들어 설명하면 3 2 1 1 9 라는 입력이 있다고 하자
정렬을 통해 1 1 2 3 9가 된다.
1) target = 1 +
1
= 2
1은 만들 수 있으니 다음 타겟인 2로 넘어감
2) target = 2 +1
= 3
위에서 1을 만들 수 있고, 여기서 1을 더하면 2이므로 1~2까지는 만들 수 있음. 따라서 다음 타겟인 3으로 넘어감
3) target = 3 +2
= 5
위에서 1~2까지 만들수 있고, 1~2에 각각 2를 더하면 3~4도 만들 수 있으므로 1~4까지 만들 수 있다. 따라서 다음 타겟인 5로 넘어감
3) target = 5 +3
= 8
1~4까지 만들 수 있고 1~4에 각각 3을 더하면 4~7도 만들 수 있으므로 1~7까지 만들 수 있을 것이다. 따라서 다음 타겟인 8로 넘어감
4) target <coin[i]
(=9)이므로 break;
1~7까지 만들수 있고 1~7에 각각 9를 더하면 10~16까지 만들 수 있다. 그러나 8과 9는 만들 수 없게 된다. 따라서 현재 타겟인 8이 만들 수 없는 금액의 최솟값이 된다.
솔직히 풀이를 봐도 뭔소리인지 몰라서 한참을 들여다 보았다. 이제 이해는 됐는데 나중에 이걸 생각해내기에는 쉽지 않을 것 같다...
선생님, 안녕하세요? 해당 문제 해설에서 이해가 안가는 부분이 있어 질문이 있습니다. 다름이 아니라 '풀이' 부분의 4) 설명에서 8, 9 만들 수 없다고 하셨는데, 왜 9까지 만들 수 없다고 생각하셨는지 혹시 설명해주실 수 있으실까요...?? 9는 만들 수 있는 거 아닌가요..? 알려주시면 정말 감사하겠습니다!