만들 수 없는 금액

문제 설명

N개의 동전이 주어질 때, 만들 수 없는 양의 정수 금액 중 최솟값을 구하여라.

<제한 사항>
시간 제한 : 1 sec
메모리 제한 : 128 MB

<입력>
첫째 줄에 동전의 개수 N이 주어진다. (1 <= N <= 1000)
두 번째 줄에 각 동전의 화폐 단위를 나타내는 N개의 자연수가 공백으로 구분되어 주어진다.(각 화폐 단위는 1000000 이하의 자연수)

<출력>
만들 수 없는 양의 정수 금액 중 최소 금액 출력

<예시>
5
3 2 1 1 9

5
1 2 3 4 5
16

나의 풀이 (실패)

1. n개의 동전들로 동전 1개 만으로의 모든 조합, 2개, ..., n개 모두로 만든 조합을 하나씩 새로운 리스트(arr2)에 더하는 식으로 저장한다.
2. 집합(arr3)에 arr2의 길이만큼 반복하며 arr2의 각 item의 sum값을 넣는다.
3. arr3를 리스트로 만들어 정렬한다.
4. arr3을 선형탐색 하면서 전 item과의 차가 1이 아니면(둘 사이에 정수가 있다는 뜻) 전 item + 1을 출력하고 반복문을 빠져나온다.
5. 반복문을 다 빠져나올 때까지 반복문을 빠져나오지 않았다면 arr3의 최대값 + 1을 출력한다.

주어진 예시에서는 돌아갔으나 n = 1000을 넣어보니 시간이 거의 무한대로 늘어나 돌아가지 않았다. 당연하게도 1번에서부터 사실 nC1 + nC2 + ... + nCn 의 시간복잡도를 가지기에 O(2^n)의 지수시간, 최악의 시간복잡도를 가진다. 그리고 또 사실 동전 1000개가 (1, 300000, 300000, ..., 300000)이라하면 답은 2일 뿐 저 모든 동전을 다 조합할 필요는 없다. 세 개의 긴 자료구조도 비효율적이다.

import itertools

n = int(input())
arr = list(map(int, input().split()))

arr2 = list()

for i in range(1, n+1):
    arr2 += list(itertools.combinations(arr, i))
arr3 = set()
for i in range(len(arr2)):
    arr3.add(sum(arr2[i]))
arr3 = sorted(list(arr3))
for i in range(1, len(arr3)):
    if arr3[i] - arr3[i-1] != 1:
        print(arr3[i-1] + 1)
        break
    if i == len(arr3) - 1:
        print(arr3[i] + 1)

책 풀이

1. 동전 정보를 오름차순으로 정렬.
2. n까지 만들 수 있고, 그 다음 동전의 단위가 x 이면 n + x까지는 당연히 만들 수 있다.(동전의 단위가 각각 1, 2, 3인 동전 세 개가 있어서 6까지 만들 수 있고 단위 6의 동전이 추가된다면 1~12까지는 만들 수 있다. -> {1,2,3,4,5,6} + 6)
3. n까지 만들 수 있고, 그 다음 동전의 단위가 n+1을 초과하면 n+1은 만들 수 없다.

n = int(input())
data = list(map(int, input().split()))

data.sort()
print(data)

target = 1
for x in data:
    if target < x:
        break
    target += x

print(target)

느낀 점

아무리 그리디 알고리즘이라 하더라도 처음부터 너무 무식하게 생각했고, 시간복잡도를 처음부터 고려하지 않았다.

출처 : 이것이 취업을 위한 코딩테스트다 with 파이썬 - 나동빈