백준 - 저울(Swift)

백준 - 저울(Swift)

 

 

 문제 설명

 

https://www.acmicpc.net/problem/2437

2437번: 저울

 

 나의 풀이

 

이 문제의 첫번째 접근은 동떨어진 숫자는 제외해도 된다는 것이다.

예를 들어 1, 2, 3, 200이라는 숫자가 있을때 200을 제외하고 만들 수 있는 가장 최소값은 7이다.

1, 2, 3, 4, 200의 경우에도 200을 제외하고 만들 수 있는 가장 최소값은 11이다. 

 

그리고 이렇게 예시를 보면서 또 하나 알게된 것이 있는데 맨 앞자리부터 누적한 값들 + 1이 최소값이 되는 것이다.

 

그럼 1, 2, 5의 예시를 살펴보자.

이 수들의 만들 수 있는 최소값은 4이다. 만약 1, 2, 4가 왔다면 8이 되었을 것이다.(1~8까지 전부 만들 수 있다.)

즉 누적합+1까지는 만들 수 있는 수들이고 누적합+2가 된다면 누적합+1을 구하지 못하기 떄문에 이 부분이 break시점이 되는 것이다.

 

import Foundation

let n = Int(readLine()!)!
var arr = readLine()!.components(separatedBy: " ").map{Int($0)!}
arr.sort(by: <)
var sum = 0 // 누적합

for x in arr {
    // 누적합+1보다 큰 수가 나온다면 break
    if x > sum+1 {
        break
    }
    sum = sum + x
}

print(sum+1)