[백준] 2437번 저울 (Python)

백준 2437번 저울

DP로 해결해야 하나 고민했던 문제다. 하지만 주어진 list의 길이를 보아하니 사용한 추와 사용하지 않은 추를 구분하여 해결할 수 없는 문제임을 깨달았다. 같은 이유로 BFS 탐색 또한 불가능할 것이라고 생각했다. 추의 무게를 높이로 생각했을 때 연속적으로 표현할 수 있는 높이의 최솟값을 구하는 문제로 다르게 생각했고, 내가 파악은 문제의 포인트는 이러하다.

1. 1부터 1씩 점차 증가하여 만들 수 없는 수를 찾아야 한다.
2. n까지 만들 수 있는 상황에서 w라는 추를 갖고 있다면, p + w 까지의 수는 무조건 만들 수 있다는 뜻이다.

이러한 특성을 토대로 만든 솔루션은 이와 같다.

1. 추를 오름차순으로 정렬한다.
2. n은 1부터 시작하고, 추 list를 탐색하며 현재 사용할 수 있는 새로운 추 중에 최솟값인 w가 n 보다 크다면, n을 만들 수 있는 방법이 존재하지 않으므로 반복문을 종료한다.
3. n 보다 작거나 같다면 현재까지 만들어낼 수 있는 무게는 n + w이다.

import sys

a = int(sys.stdin.readline().strip())
wList = list(map(int, sys.stdin.readline().split()))
wList.sort()
n = 1
p = 0
while p < a:
    if n >= wList[p]:
        n += wList[p]
        p += 1
    else:
        break
print(n)