백준 2437번 저울 - SWIFT

문제

---

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다.

 

 

무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.

예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다.

 

입력

첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 무게를 나타내는 N개의 양의 정수가 빈칸을 사이에 두고 주어진다. 각 추의 무게는 1이상 1,000,000 이하이다.

 

출력

첫째 줄에 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력한다.

 

문제 링크

2437번: 저울

 

 

풀이

---

접근법을 모른다면 손도 대기 힘든 문제라고 생각했다.

필자도 접근법을 몰라서 한참 고민하다가, 지금 실력으로는 풀지 못하는 문제라고 판단하여 접근법을 검색해봤다.

접근법은 정말 어려웠다고 생각했지만, 그에 비해 구현및 풀이는 엄청나게 쉬웠다.

 

접근법

예전에 N의 최댓값이 20인 비슷한 문제를 푼 적이 있었다.

그때는 브루트포스로 모든 경우를 조사하여 해결했는데, 전체 경우가 2의 20승이라 시간내로 구할 만 했다.

하지만 지금은 N의 최댓값이 1000이다.

2의 1000승은 UInt64범위로도 표현할 수 없다.

그러면 이 문제를 어떻게 접근해야할까?

 

바로 수학적 귀납법으로 접근해야한다.

 

일단 추의 무게를 정렬하자.

그리고 가장 앞의 값부터 차례로 추의 무게를 더해본다.

만약 가장 앞의 값이 1이 아니라면, 추의 무게를 빼는 연산은 없으므로 1이 답이 될 것이다.

하지만 1이 있다면, 본격적으로 귀납적으로 접근하게 된다.

추의 무게가 이렇게 있다고 하자.

그리고 추의 무게 합을 sum이라고 하겠다.▼

 

 

그러면 맨 처음에는 지목한 추와 sum은 이렇게 될 것이다.

추를 다 더해서 얻은 값인 sum은 우리가 만들 수 있는 수다.▼

 

 

우리가 현재 가지고 있는 수는 1이고, 1 다음 수는 2이므로 우리는 다음에 2 이하의 수가 오지 않는한, 다음 수를 구현할 수 없다.

이를 수학적 귀납법으로 정리하면, 배열 다음 값이 sum + 1보다 크다면, sum + 1 값은 구현할 수 없는 수가 된다.▼

 

 

다음 수가 2보다 작은 1이므로, 이제 1과 1을 더해 2를 구현할 수 있게 되었다.

즉, sum의 값은 구현할 수 있는 수의 최댓값을 말하는 것이다.▼

 

 

그러면 현재 우리는 1 두 개의 합으로 2를 구현할 수 있게 되었다.

하지만 우리가 가진 추는 현재 1 두개이므로, 3을 구현할 수 없다.

그래서 3을 구현하려면, 3이 다음 수로 나오거나, 3보다 작은 수가 나와서 3을 만들 수 있게 해줘야한다.

이는 역시 앞에서 말한 배열 다음 값이 sum + 1보다 크다면, sum + 1 값은 구현할 수 없다는 말과 같다.

그럼 다음 수를 확인해보면, 3보다 작은 2이다.

이를 통해 우리는 2 + 1 + 1 까지의 수를 구현할 수 있게 된 것이다.▼

 

 

여기까지 보면, 수학적 귀납법을 통해 배열 다음 값이 sum + 1보다 크다면, sum + 1값은 구현할 수 없다는 것이 통하게 된다.

그래서 sum + 1보다 큰 값이 나올 때 까지 sum에 값을 더하면서 배열 인덱스값을 늘려보겠다.▼

 

 

모든 추를 사용해서 만든 값이 20인데, 다음에 21보다 큰 값이 오게되면 더이상 연속해서 수를 만들어낼 수 없게 된다.

다음 수가 30이므로, sum + 1의 수는 만들 수 없게된다.

그러므로 만들지 못하는 다음 수는 21이 된다.▼

 

 

프로그램 동작

---

앞의 접근법을 보면 알겠지만, 접근법이 곧 프로그램 동작 과정이다.

추를 계속 더해나가면서 다음 수가 합계보다 큰지 작은지만 체크해주면 된다.

접근법은 꽤나 이해를 요하는 방법이었지만, 그에 비해 구현은 너무나도 쉽게 할 수 있다.

 

 

Swift 코드

---

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

weight.sort()

if weight[0] != 1 {
    print(1)
} else {
    var sum = weight[0]

    for i in 1..<N {
        if weight[i] > sum + 1 {
            break
        }
        sum += weight[i]
    }
    print(sum + 1)
}