백준 2437 저울

출처: www.acmicpc.net/problem/2437

분류: 그리디

---

접근방식

쉬워보였으나, 실제로도 방법만 알면 쉬우나, 쉽지 않았던 문제입니다 😭

추들이 주어질 때 측정할 수 없는 최소값을 구하는 문제입니다.
어떤 경우가 되면 더 이상 무게를 구할 수 없다고 판단할 수 있을까요?

추를 오름차순으로 정렬했을 때,

처음 추의 무게가 2라면, 절대 1은 만들 수가 없습니다. 
1, 2 다음에 900이 나온다면? 최대로 3까지 만들 수가 있습니다.
1, 2, 3 다음에 900이 나온다면? 최대로 6까지 만들 수가 있습니다.

그렇다면 이제 다시 생각해볼까요? 저희는 직관적으로 알고 있습니다.

1, 2, 3 다음에 900이 나오면, 이미 900은 너무 큰 숫자니 제치고 그 전의 1, 2, 3가지고 최대를 찾아야 한다는 걸 말이죠!

현재까지 확인된 추의 총 합이 최대로 측정할 수 있는 무게가 됩니다. 이걸 다른 말로 누적합 이라고 할 수 있겠죠.
누적합+1 까지는 누적합 다음 수가 자신이기 때문에 괜찮지만
여기서 다음 추가 누적합+2 라면 어떻게 될까요? 아쉽게도 누적합+1을 표현할 수 있는 방법이 없게됩니다.

그럼 누적합+2 이상이 들어오면 안되는 건 알겠는데 누적합으로 그 사이의 값들을 다 보장할 수 있을까요?
저는 이게 가장 큰 의문이었습니다...

오름차순으로 1부터 차례대로 확인해왔기 때문에 이를 확인할 수 있습니다.
현재 들어온 수가 누적합+2로 오면 안되는 숫자만 아니라면, 그 사이의 수는 어떻게는 만들 수가 있습니다.

1 2 3 3 3 으로 누적합이 12인 상황에서 다음으로 13이 들어왔다고 생각해봅시다.
13은 누적합+1 이므로 올 수 있는 숫자입니다. 13이 추가되므로써 누적합은 25가 되죠.
이제 13 ~ 25 까지의 수를 다 만들 수가 있는지 확인해보면 되겠죠?

14를 만든다고 생각해봅시다. 13이 새로 추가됐으므로 그전에 만들어뒀던 1을 가져다 붙일 수가 있습니다.

20을 만든다고 생각해볼까요? 역시 13이 새로 추가됐으므로 그전에 언젠가 만들어뒀던 7을 가져다 붙을 수가 있습니다.

다시한번, 저희가 1부터 차례대로 확인해왔기에 가능한 일이 되는거죠.

 

해결방법

다들 쉽게 이해하셨을 수도 있는데 저는 이게 이해가 안되서 한참을 고민했었습니다.. 그래서 사족이 좀 길었네요 ㅎㅎ

이해만 하셨다면 풀이 자체는 간단합니다.

// 입력
let n = Int(readLine()!)!
var weights = readLine()!.split(separator: " ").map { Int($0)!}

// 오름차순 정렬
weights.sort()

var totalSum = 0 // 누적합

for weight in weights {
    if weight > totalSum+1 {
    	// 추가 누적합 + 2 이상이라면 합을 더하지 말고 종료합니다.
        break
    }
    totalSum += weight
}

print(totalSum+1)

배운점

초등부 3번 문제인데... 저희 나라의 미래는 밝네요 ㅎ

화이팅 또 화이팅입니다.. 😢