문제 :
편의점 주인인 동빈이는 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 int n;
public static ArrayList<Integer> arrayList = new ArrayList<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (int i = 0; i < n; i++) {
arrayList.add(sc.nextInt());
}
Collections.sort(arrayList);
int target = 1;
for (int i = 0; i < n; i++) {
// 만들 수 없는 금액을 찾았을 때 반복 종료
if (target < arrayList.get(i)) break;
target += arrayList.get(i);
}
System.out.println(target);
}
}문제풀이
현재 확인하는 동전을 이용해 target 금액을 만들 수 있는 조건 :
기존 target 값 >= 현재 확인하는 동전 값
target 업데이트 방식 :
기존 target 값 + 현재 확인하는 동전 값
1) 기존 target 값 < 현재 확인하는 동전 값
기존 target 값이 8, 현재 확인하는 동전 값이 10이라고 가정하자.
기존 target 값이 8이므로 1~7까지 만들 수 잇다.
현재 확인하는 동전 값 10을 이용하면 10~17을 만들 수 있으므로 기존 target 값인 8을 만족시킬 수 없다.
즉, 8이 결과 값이 된다.2) 기존 target 값 == 현재 확인하는 동전 값
기존 target 값이 10, 현재 확인하는 동전 값이 10이라고 가정하자.
기존 target 값이 10이므로 1~9까지 만들 수 잇다.
현재 확인하는 동전 값 10을 이용하면 10~19을 만들 수 있으므로 기존 target 값인 10을 만족한다.
target 값은 20(기존 target 값 10 + 현재 확인하는 동전 값 10)으로 업데이트 하면 된다.3) 기존 target 값 > 현재 확인하는 동전 값
기존 target 값이 10, 현재 확인하는 동전 값이 8이라고 가정하자.
기존 target 값이 10이므로 1~9까지 만들 수 있다.
현재 확인하는 동전 값인 8을 이용한다면 8~17을 만들 수 있으므로 기존 target 값인 10을 만족한다.
target 값은 18(기존 target 값 10 + 현재 확인하는 동전 값 8)으로 업데이트 하면 된다.
