[Backjoon] 저울

 

백준 2437번 저울 문제는 정렬을 이용해서 풀 수 있는 그리디 알고리즘 문제이다. 주어진 추들을 정렬하고 추들을 이용해서 만들 수 없는 무게의 최소값을 찾는 문제이기 때문에 역순으로 정렬하여 접근했다. 처음 풀이에서는 최소값을 1씩 늘려가면서 순회하느라 시간초과가 발생했다. 그러나 추들의 무게를 더해주면서 최소값을 찾으면 정답을 얻을 수 있다.

아래는 풀이법이다.

 

import sys

if __name__ == "__main__":
    cases = int(sys.stdin.readline())
    weight = list(map(int, sys.stdin.readline().split(" ")))

    weight.sort(reverse=True)

    num_check = 1
    while True:
        target = num_check
        for idx in range(cases):
            if weight[idx] == target:
                target -= weight[idx]
                
                # 최소값을 찾을 때 추의 무게를 더해준다.
                num_check += weight[idx]
                break
            elif weight[idx] < target:
                target -= weight[idx]

        if target > 0:
            break

    print(num_check)