[백준/BOJ] 2437번: 저울

문제

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

2437번: 저울

해설

문제의 예시를 봐보자.

3, 1, 6, 2, 7, 30, 1이 있을 때 이를 오름차순으로 정렬해보면 1, 1, 2, 3, 6, 7, 30이 된다.

만약 가장 가벼운 추에 1이 없다면, 우리가 측정 못하는 가장 작은 무게는 1이 된다.

 

차례대로 봐보면,

첫번째 추로 1을 측정할 수 있다.

두번째 추를 이용해 2도 측정할 수 있다.

세번째 추를 이용하여 3, 4를 측정할 수 있다.

4번째 추를 사용하면 5, 6, 7까지 측정이 가능하다.

 

이쯤에서 규칙을 생각해볼 수 있다.

무게의 총합을 sum이라고 하자. 이때 위에서도 보았듯이 가장 작은 추를 고려하여 초기값을 1로 한다.

1번째 추일 때는 1까지만 측정할 수 있었다. -> (추)1 ≤ (sum)1

2번째 추일 때는 2까지 측정 가능했다. -> 1  ≤ 1+1 = 2(앞에서 추 1을 놓았으므로)

3번째 추일 때는 4까지 측정이 가능하다. ->  2 ≤ 1 + 1 + 2 = 4

4번째 추일 때는 7까지 측정이 가능하다. ->  3 ≤ 1 + 1 + 2 + 3

즉, 추의 무게가 이전까지의 합보다 작을 때만 측정이 가능하다.

 

예를 들어 30을 보자.

1+1+2+3+6+7 = 20이다.

이때 다음에 올릴 수 있는 무게는 30이다. 즉, 21 ~ 29는 무게를 측정할 수 없다.

코드

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val weight = readLine().split(" ").map { it.toInt() }.sorted()
    println(solve(weight))
}

fun solve(weight: List<Int>): Int {
    var sum = 1

    run {
        weight.forEach {
            if(sum < it) return@run
            sum += it
        }
    }

    return sum
}