[BOJ] #2437 저울 (Python, Greedy)

🌱 문제

2437번: 저울

 

🌱 풀이

0. 접근하기

문제 예시에서 추가 1, 1, 2, 3, 6, 7, 30일 때, 정답이 21입니다. 이를 추의 배열이 [1, 1, 2, 3, 6, 7, 30]일 때 앞에서부터 차례대로 더한 값의 배열은 [1, 2, 4, 7, 13, 20, 50]입니다. 정답이 21임을 아는 상태에서는 1-20까지의 무게는 무조건 만들 수 있다고 판단할 수 있습니다. 이 때 1부터 20까지는 무조건 만들 수 있으므로 31부터 50까지도 무조건 만들 수 있음을 알 수 있습니다.(만들 수 있는 무게에 30을 더함) 또한, 1부터 13까지 무조건 만들 수 있다고 한다면 7을 더한 20까지도 무조건 만들 수 있다는 것을 알 수 있습니다. 이 아이디어를 이용해서 문제를 풀 수 있습니다. 관건은 "여기까지는 무조건 만들 수 있는 무게다!"라는 것을 확인하는 것입니다.

그것을 확인할 수 있는 것은 이전 상태까지 만들 수 있는 무게가 다음 추보다 크거나 같아야 합니다. 예시를 들어보겠습니다.

• 추가 [1, 1, 2, 3, 6, 7, 30]이면 7과 30사이에 만들 수 있는 무게에 빈공간이 생깁니다.
• 추가 [1, 1, 2, 6, 7, 8, 30]이면 2와 6사이에 만들 수 있는 무게에 빈공간이 생깁니다. 

즉, 빈공간없이 무게가 만들어지려면 이전 추가 만들 수 있는 무게의 최댓값이 다음 추의 무게보다 크거나 같아야 합니다. 이 예시에서는 무게가 2인 추가 만들 수 있는 무게는 3부터 4인데, 최댓값인 4가 다음 추의 무게인 6보다 작으므로 빈공간이 생기게됩니다.

1. 추의 무게 정렬하기

추의 무게를 오름차순으로 정렬 후, 하나씩 꺼내오며 만들 수 있는 무게를 결정지어야 어디에서 만들 수 없는 무게가 생기는 지 알 수 있습니다.

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

2.

num = 1
for i in range(n):
    if num < weights[i]:
        break
    num += weights[i]
print(num)

추를 하나씩 돌면서 이전 상태에서 만들 수 있는 무게의 최댓값(num)보다 현재 추의 무게(weights[i])가 크면 정답을 출력합니다.

 

🌱 코드

# !/usr/bin/env python
# -*- coding: utf-8 -*-
# boj 2437 저울

from itertools import combinations
import sys
input = sys.stdin.readline

n = int(input().rstrip())
weights = list(map(int, input().split()))
weights.sort()

num = 1
for i in range(n):
    if num < weights[i]:
        break
    num += weights[i]
print(num)

 

+) 참고한 블로그

BOJ 2437번 저울 [그리디 알고리즘]