[BOJ 2437 - 저울]

문제

문제 보러가기: BOJ 2437

양팔 저울의 한 쪽에만 저울 추를 올려 다른 쪽의 무게를 측정할 수 있고, 저울 추의 개수 N과 각각의 무게가 주어졌을 때,
추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 구하라.

조건

• N은 1 이상 1,000 이하
• 각 추의 무게는 1이상 1,000,000 이하
  
  

예제

풀이

접근

1. dfs를 사용해 추의 무게를 계산한다.
   : 조합을 일일이 구하며 계산해야 하므로 시간복잡도가 엄청 커짐
2. 부분합을 사용해 추의 무게를 계산한다.
   : 연속적으로 조합할 필요 없으므로 부분합으로 계산하는 것은 무의미함
3. 조합을 사용해 추의 무게를 계산한다.
   : 최악의 경우 1000!/(500!500!)의 조합을 계산하므로 메모리, 시간 모두 초과함
4. 추의 무게 범위를 계산한다. (Adopted)

추의 무게 범위를 계산해보자

위의 그림에서와 같이 만약 무게 1의 추가 하나 있어 양의 정수 1까지의 범위를 커버할 수 있었다고 해보자.

이때, 무게 2의 추가 생긴다면, 양의 정수 1까지의 범위와 새로운 추에서 가능한 2-3의 범위가 커버된다. 이때 3은 새로운 추의 무게 2와 이전까지의 추의 범위의 최댓값인 1이 더해진 것이다. 따라서 정수 1, 2, 3이 모두 커버된다.

이때, 무게 2의 추가 아닌 무게 3의 추가 생긴다면, 양의 정수 1까지의 범위와 새로운 추에서 가능한 3-4 범위가 커버된다. 이때 4는 새로운 추의 무게 4과 이전까지의 추의 범위의 최댓값인 1이 더해진 것이다. 따라서 정수 1, 3, 4가 커버된다.

이처럼, 추가 하나씩 더 생길 때, 커버 가능한 구간이 불연속인 경우를 고려하면 문제를 해결할 수 있다.

코드

# input
N = int(input()) #1000
weights = list(map(int, input().split()))
weights.sort()

# solution
# 작은 추부터 추가하면서, 추가 하나 추가될 때마다 측정할 수 있는 범위를 늘린다!
# 이때 끊어지는 부분이 생기면 ans
len = 0
for i in range(N):

    if weights[i] - len <= 1:
        len += weights[i]
    
    else:
        break

# ouput
print(len + 1)

---

• 참고자료
• sort, greedy
• Self-feedback
  간단하게 생각해보기
  별개로 dfs/bfs 연습 더 하기