[백준 2437번] 저울 - 파이썬

 

문제 링크:

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

2437번: 저울

 

---

풀이 과정:

이 문제는 무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구해야 하는 문제이다.

이 문제의 핵심은 다음과 같다.

1. 데이터를 오름차순으로 정렬

2. target = 1이라는 변수를 만들어 만들 수 없는 금액을 표기하기

3. target이 특정 데이터 값과 비교했을 때 작다면 target값이 만들 수 없는 금액의 최솟값

4. target값 출력

 

예를 들어..

데이터가 1, 6, 2, 3이 있다고 하자.

이를 오름차순 정렬하면 1, 2, 3, 6이 되고, 수를 더해서 만들 수 없는 숫자(target)는 13(1+2+3+6+1)

이 된다.

다음을 통해 target에 대해 이해해보자.

<만들 수 없는 숫자의 최솟값(target)을 도출하기 위해 1부터 수를 차례대로 1씩 증가시키기>

1 = 1 , 2 = 2, 3 = 3, 4 = 1+3,
5 = 2+3, 6 = 6, 7 = 1+6, 8 = 2+6,
9 = 3 + 6, 10 = 1+3+6, 11 = 2+3+6, 12 = 1+2+3+6

 

1부터 12까지는 모두 주어진 수(1, 2, 3, 6)로 만들 수 있지만, 13은 만들 수 없다.

이제 코드를 작성해보자.

 

풀이 코드:

# 2437번 저울
n = int(input())
data = list(map(int, input().split()))
data.sort()

target = 1
for x in data:
    # 만들 수 없는 금액을 찾았을 때 종료
    if target < x:
        break
    target += x
    
# 만들 수 없는 금액 출력
print(target)

 

백준 2437번 저울