[백준] 2437 저울 (파이썬)

골드 Ⅱ

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

2437번: 저울

 

📄 문제

• 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다.
• 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다.

 

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

 

---

💡 아이디어

• 그리디 알고리즘이다.
• 추의 무게를 오름차순으로 정렬한다.
• 적은 무게부터 더해가며 측정할 수 없는 무게를 찾는다.
• 즉, 측정할 수 있는 무게가 끊어지지 않게 이어나가는 것이 중요하다.
• 현재 측정가능한 구간에서 다음 무게를 더했을 때 끊어지는 값이 없어야 한다.
• 지금까지 올린 추의 총 합(누적합) + 1 보다 새로 올리려는 추의 무게가 크면, 지금까지 올린 추의 총 합(누적합) + 1이 측정할 수 없는 최솟값이 된다.

 

그래프로 예를 들면,

1부터 6까지 측정 가능한 무게를 구했다고 가정할 때, 

다음 순서의 저울 추 무게가 7 이하 이면 측정 가능한 무게를 이어나갈 수 있다.

 

측정 가능한 구간이 [1, 2, 3, 4, 5, 6] 일 때,

 

1. 다음 저울 추의 무게가 3이면, [1, 2, 3, 4, 5, 6, 4+3, 5+3, 6+3]으로 9까지 가능하다. 

 

1	2	3	4	5	6	7	8	9	...
현재 측정 가능한 구간
			다음 저울 추가 3일 때, 측정 가능한 구간

 

2. 7이면, [1, 2, 3, 4, 5, 6, 7, 1+7, 2+7, ~, 5+7, 6+7]으로 13까지 가능하다.

 

1	2	3	...	6	7	8	...	13	...
현재 측정 가능한 구간					다음 저울 추가 7일 때, 측정 가능한 구간

 

 

3. 하지만, 다음 순서의 추 무게가 8 이상이면 7은 측정할 수 없다.

 

1	2	...	6	7	8	9	...	14	...
현재 측정 가능한 구간				측정 불가	다음 저울 추가 8일 때, 측정 가능한 구간

 

4. 9 이상이면, 7, 8은 측정할 수 없다.

 

1	2	...	6	7	8	9	...	15	...
현재 측정 가능한 구간				측정 불가		다음 저울 추가 9일 때, 측정 가능한 구간

 

예제로 상세하게 예를 들면,

저울 추의 무게를 오름차순으로 정렬하면 아래와 같다.

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

 

누적합의 변수명은 ssum이라고 한다. (ssum까지 무게를 측정할 수 있음을 나타낸다.)

 

1. ssum = 0 (시작)
   • 인덱스 0, 무게 1인 저울 추는 ssum + 1 = 1보다 크지 않기 때문에 무게 1부터 측정할 수 있다.
   • 따라서, ssum에 첫 번째 추의 무게 1을 더해준다. (ssum = 1)
2. ssum = 1 (구간 [1])
   • 인덱스 1, 무게 1인 저울 추는 ssum + 1 = 2보다 크지 않기 때문에 무게 1에 이어서 무게를 측정할 수 있다.
   • 따라서, ssum에 두 번째 저울 추의 무게 1을 더해준다. (ssum = 2)
3. ssum = 2 (구간 [1, 2])
   • 인덱스 2, 무게 2인 저울 추는 ssum + 1 = 3보다 크지 않기 때문에 무게 2에 이어서 무게를 측정할 수 있다.
   • 따라서, ssum에 세 번째 저울 추의 무게 2를 더해준다. (ssum = 4)
4. ssum = 4 (구간 [1, 2, 3, 4])
   • 인덱스 3, 무게 3인 저울 추는 ssum + 1 = 5보다 크지 않기 때문에 무게 4에 이어서 무게를 측정할 수 있다.
   • 따라서, ssum에 네 번째 저울 추의 무게 3을 더해준다.  (ssum = 7)
5. ssum = 7 (구간 [1, 2, 3, 4, 5, 6, 7])
   • 인덱스 4, 무게 6인 저울 추는 ssum + 1 = 8보다 크지 않기 때문에 무게 7에 이어서 무게를 측정할 수 있다.
   • 따라서, ssum에 다섯 번째 저울 추의 무게 6을 더해준다.  (ssum = 13)
6. ssum = 13 (구간 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13])
   • 인덱스 5, 무게 7인 저울 추는 ssum + 1 = 14보다 크지 않기 때문에 무게 13에 이어서 무게를 측정할 수 있다.
   • 따라서, ssum에 여섯 번째 저울 추의 무게 7을 더해준다.  (ssum = 20)
7. ssum = 20 (구간 [1, 2, 3, 4, 5, 6, 7,..., 18, 19, 20])
   • 인덱스 6, 무게 30인 저울 추는 ssum + 1 = 21보다 크다.
   • ssum에 일곱 번째 저울 추의 무게 30을 더하면 1 ~ 20, 30 ~ 50의 두 구간으로 나뉘어 측정된다.
   • 두 구간은 연속되지 않으므로, 21~29까지의 무게는 측정 불가능하다.
   • 따라서, 측정 불가능한 최소 무게는 21이다.

 

---

처음에는 가능한 모든 무게의 합을 저장하고 1부터 순서대로 확인하면서 없는 값을 찾았다.

당연히.. 시간 초과가 나왔고 누적합이나 DP를 이용해야 할 것 같은 느낌이 들었다.

하지만, 더 이상 방법이 떠오르지 않았고 아이디어를 생각해 내기 너무 어려운 문제였다.

 

📝 문제 풀이 (Code)

n = int(input())
weights = sorted(map(int,input().split()))

# 누적합 저장
ssum = 0

for weight in weights:
    # 현재 누적합에 1을 더한 값 보다 크면
    # 구간을 이어서 무게를 만들수 없다.
    if ssum + 1 < weight:
        break
    
    # 작거나 같으면
    # 무게가 계속 연속되어 이어진다.
    ssum += weight

print(ssum + 1)

---

참고 풀이 방법

https://plplim.tistory.com/59

https://aerocode.net/392