[알고리즘 문제] 카드 더하기 (Python / 파이썬)

문제

유니는 오늘 학교에서 덧셈을 배웠다.
유니의 집에는 N장의 카드가 있는데, 각 카드에는 1보다 크거나 같고 1,000,000 보다 작거나 같은 정수가 하나씩 적혀 있다. 유니는 이제 이 카드 중 일부를 골라서 더하면 새로운 수를 만들 수 있다는 것을 안다. 하지만 카드가 무한하지 않기 때문에 만들지 못하는 수도 존재한다는 것을 알았다.
카드에 적힌 수가 주어질 때, 유니가 카드를 어떻게 골라서 더해도 만들 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트케이스의 수 T가 주어진다..
각 테스트케이스의 첫 줄에 N이 주어진다.
각 테스트케이스의 둘째 줄에 카드에 적힌 번호가 공백으로 구분되어 주어진다. 각 카드에 적힌 수는 1 이상 1,000,000 이하의 자연수다.
( 1 ≤ T ≤ 10, 1 ≤ N ≤ 1,000 )

출력

각 테스트케이스마다 '#'과 테스트케이스의 번호, 공백을 출력한 뒤 유니가 만들 수 없는 가장 작은 수를 출력한다.

---

문제 풀이

정수가 하나씩 적혀있는 N장의 카드 중 카드를 골라 더했을 때

절대 만들 수 없는 최소의 수를 구하는 문제이다. 

 

먼저, 1을 만들 수 있는지 확인하기 위해 초기 값을 1로 설정해준다. 

만약 카드에 적혀있는 수가 

7 1 6 3 4 4 6 6 9 8 이라고 할 때, 수를 오름차순으로 정렬해준다. 

이제 오름차순한 결과의 첫번째 값과 1을 비교한다. 

1 3 4 4 5 5 5 7 8 9 

첫번째 값이 1이므로 1을 만들 수 있다. 따라서 첫번째 값과 1을 더해준다. 

그럼 2가 되는데 이 의미는 1까지 수를 만들 수 있으니

2를 만들 수 있는지 확인하겠다는 것이다. 

다음 수는 3이다. 2보다 큰 수는 2를 만들 수 없다. 따라서 2를 출력해준다. 

 

즉, 계속해서 배열의 값을 더해주다가 만약 더한 값보다 더 큰 수가 나오면 출력해준다. 

---

My Code

for tc in range(int(input())):
    n = int(input()) # 카드의 수

    data = list(map(int,input().split())) # 카드에 적힌 번호
    data.sort() # 오름차순으로 정렬

    target = 1 # 1부터 확인
    for x in data:
        if x > target: # 더한 결과보다 더 크다면
            break      # 만들 수 없는 수이므로 종료
        target += x    # 만들 수 있는 수이면 더해줌 
    
    print('#' + str(tc + 1), end = ' ')
    print(target)