백준 2437 저울

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

주어진 저울추들(최대 1,000개)로 측정할 수 없는 정수 무게 최솟값을 구하는 문제이다.

저울추가 3, 1, 6, 2, 7, 30, 1 총 7개가 주어진 경우.

1	2	3	4	5	6	7
1(1)	1(2)	1(1) 2(1)	1(1) 3(1)	3(1) 2(1)	6(1)	7(1)

이런 식으로 자연수 1부터 가능한 지 찾아야 한다.

처음 생각한 단순한 알고리즘은 다음과 같았다.

• 먼저, 주어진 저울추를 무게 오름차순으로 정렬한다.
  1, 1, 2, 3, 6, 7, 30

• set을 하나 생성하여 맨 앞의 1을 넣고 현재 MAX값을 1로 설정한다.

• 두 번째 원소(1)부터 set의 모든 원소에 더한 값을 다시 set에 넣는다. 여기서 더한 값이 현재 MAX값 + 1보다 크면 종료한다.

단순한 알고리즘이지만, 공간 복잡도를 간과했다.

운이 없을 경우, 각 저울추마다 set 크기가 2배씩 늘어나 지수적으로 메모리량이 증가해 초과가 날 수 있었다.

그래도 위 알고리즘을 통해 문제의 핵심을 파악할 수 있었다.

추 하나를 추가하면서 현재 MAX값을 갱신하는 것, 그리고 1부터 현재 MAX값 이하의 무게는 반드시 만들 수 있다는 것이다.

무슨 말이냐면 현재 MAX값이 10이라면 다음 추가 7의 무게일 때, 앞의 추들로 무게 4를 만들어 4 + 7로 MAX + 1인 11을 만들 수 있다는 얘기이다.

일반화 해보자면, 현재 MAX값이 m일 때 다음 무게의 추가 m + 1 이하라면 m + 1부터 m + 다음 추 무게 만큼은 측정할 수 있다는 것이다.

그럼 각 추를 순회하며 진행할 수 있는 알고리즘은 다음과 같다.

for(0을 제외한 첫 번째 추부터 마지막 추까지){
	if(현재 추 무게 <= 현재 MAX 무게 + 1){
    	현재 MAX 무게 += 현재 추 무게
    }else{
    	현재 MAX 무게 + 1을 만들 수 없으므로 출력 후 종료
    }
}

이 알고리즘으로 예시 케이스를 풀어가 보자.

1, 1, 2, 3, 6, 7, 30

1. 첫 번째, 1로 curMax = 1
2. 두 번째, 1은 curMax + 1 = 2 이하이므로 curMax += 1 (2)
3. 세 번째, 2는 curMax + 1 = 3 이하이므로 curMax += 2 (4)
4. 네 번째, 3은 curMax + 1 = 5 이하이므로 curMax += 3 (7)
5. 다섯 번째, 6은 curMax + 1 = 8 이하이므로 curMax += 6 (13)
6. 여섯 번째, 7은 curMax + 1 = 14 이하이므로 curMax += 7 (20)
7. 일곱 번째, 30은 curMax + 1 = 21 보다 크므로 curMax + 1인 21이 정답.

갱신되는 curMax는 1 - 2 - 4 - 7 - 13 - 20이다.

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()
    val weights = readLine().split(' ').map{it.toInt()}.sorted()

    var curMax = 1
    if(weights[0] != 1){
        print(1)
        return@with
    }

    for(i in 1 until weights.size){
        if(weights[i] <= curMax + 1){
            curMax += weights[i]
        }else{
            print(curMax + 1)
            return@with
        }
    }

    print(curMax + 1)
}