문제 예시

1. 입력

7
3 1 6 2 7 30 1

2. 출력

21

---

규칙

1. 추의 개수와 각 추의 무게를 제시한다
2. 각 추를 더해 만들 수 있는 추의 무게 중 가장 낮은 무게를 찾아낸다

---

풀이

1. 만약 내가 가지고 있는 저울추들로 1~K무게를 모두 만들 수 있다고 가정

2. 저울추(L)가 K무게 보다 같거나 작다면, 다음 저울추로 (1+L)~(K+L)무게를 모두 만들 수 있다.
   그렇다면 다음 저울추까지 포함했을때 1~(K+L)무게를 모두 만들 수 있다.

예시

저울추를 오름차순으로 정렬하면:
[1, 1, 2, 3, 6, 7, 30]

• 첫 번째와 두 번째 저울추인 1, 1을 사용하면 무게 1, 2를 만들 수 있다

• 세 번째 저울추인 2를 사용하면, 현재까지의 무게(1, 2)에 각각 2를 더하여 무게 3, 4를 만들 수 있다

• 네 번째 저울추인 3을 사용하면, 현재까지의 무게(1, 2, 3, 4)에 각각 3을 더하여 무게 4, 5, 6, 7을 만들 수 있다

• 다섯 번째 저울추인 6을 사용하면, 현재까지의 무게(1~7)에 각각 6을 더하여 무게 7, 8, 9, 10, 11, 12, 13을 만들 수 있다

• 여섯 번째 저울추인 7을 사용하면, 현재까지의 무게(1~13)에 각각 7을 더하여 무게 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20을 만들 수 있다

• 이렇게 주어진 저울추를 조합하여 1부터 20까지의 무게를 모두 만들 수 있다

만약 (1 ~ 20)까지 만들 수 있는 무게에서 30을 더할 경우 30을 포함하여 (30 ~ 50)까지 만들 수 있기 때문에 (20 ~ 29) 사이의 값은 만들 수 없다

---

코드

let input = Int(readLine()!)!
var weight = readLine()!.split(separator:" ").map{Int($0)!}
weight.sort()

var x = 1
for i in weight {
    if x >= i {
        x += i
    }else {
        break
    }
}
print(x)

---

시간 줄이기 참 어렵다..