💻 입력 조건
- 첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어집니다. (1<= N <=1,000)
- 둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분합니다. 이때, 각 화폐의 단위는 1,000,000 이하의 자연수입니다.
💻 출력 조건
- 첫째 줄에 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력합니다.
💻 입력 예시
5
💻 출력 예시
3 2 1 1 9
📖 문제 해결
solution 1.
우선 입력을 받은 후 동전의 금액을 오름 차순으로 정렬을 합니다.
그 후 동전들을 이용하여 다양한 조합을 시도해 본 후에, 조합 마다의 나올 수 있는 모든 합들의 unique 한 값들을 sort 한 후 연속된 자연수들 중에서 빠져있는 수가 있다면 출력할 수 있도록 하였습니다.
위의 풀이는 itertools를 이용한 풀이인데, 회사에 따라 다르지만 itertools를 사용하지 못하게 하는 회사도 있다고 합니다. 따라서 파이썬 내장 모듈만을 이용하여 작성한 책의 코드를 다시 저의 방식으로 이해 및 해석(?) 하여 다시 작성한 코드 또한 첨부하였습니다.
solution 2.
solution 1.에서와 마찬가지로 입력을 받은 후 동전의 금액을 오름 차순으로 정렬합니다.
우선 1의 유무부터 확인합니다. 모든 자연수를 만들기 위해서 1은 반드시 포함이 되어야 하기 때문입니다. 따라서 1이 없다면 1이 정답이 됩니다.
1이 있는 지 확인한 이후, 또 1이 있다면 1과 1을 더하여 2를 만들 수 있습니다. (즉, [1,1]로부터 만들어질 수 있는 자연수는 1,2입니다.)
그리고 1이 아닌 2가 있다면 2자체만으로 2가 되고, 또 1과 2를 더하여 3도 만들 수 있습니다. (즉, [1,2]로부터 만들어질 수 있는 자연수는 1,2,3입니다.)
그러나 3부터는 조금 달라집니다. 1과 3으로는 덧셈만으로 2를 만들 수 없기 때문입니다.
이를 정리해 보면 우리가 지금까지 사용해 본 정렬된 동전들로 연속된 n까지의 자연수 금액을 만들 수 있다고 할 때, 바로 다음에 사용하고자 하는 동전이 n+1의 값을 초과한 자연수라면 우리는 n+1을 만들 수 없게 됩니다.
따라서 이때의 결과는 n+1이 되고, 이를 코드로 풀어서 작성한 것이 바로 solution 2.입니다.
# solution 1.
from itertools import combinations
N = int(input())
coins = list(map(int,input().split()))
coins.sort()
sum_list = []
for i in range(1,N):
for comb in combinations(coins,i):
sum_list.append(sum(comb))
sum_list.sort()
sum_list = list(set(sum_list))
for idx,num in enumerate(sum_list):
if (idx + 1) != num:
result = idx + 1
break
print(result)
# solution 2.
N = int(input())
coins = list(map(int,input().split()))
coins.sort()
for i in range(N):
if i == 0 :
possible = coins[i]
if possible != 1:
result = 1
break
elif (possible + 1) >= coins[i]:
possible += coins[i]
else :
result = possible + 1
break
print(result)