https://www.acmicpc.net/problem/2437
2437번: 저울
하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 골드 3 티어 문제로 저는 굉장히 어렵게 풀었던 문제입니다. 그리디 알고리즘으로 해결할 수 있는 문제인데 우선 알아야 하는 것이 있습니다. 바로 1부터 X - 1까지 만들 수 있는 금액이라고 가정을 했을 때 X가 새로 들어온 화폐단위인 a[i]보다 크다면 X원은 만들 수 없다는 것입니다. 이 경우는 저는 암기를 하기로 결정하였습니다. 크루스칼 알고리즘도 그리디이긴 하지만 암기가 필요한 부분입니다. 따라서 해당하는 경우도 암기를 바탕으로 해결합시다.
문제 해결을 위한 팁
팁까지는 아니지만 꼭 짚고 넘어가야할 조건이 있습니다. 바로 리스트가 정렬이 된 상태이어야만 한다는 것입니다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
|
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)
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 13305: 주유소(Python) (0) | 2021.01.19 |
|---|---|
| 백준 알고리즘 1715: 카드 정렬하기 (Python) (0) | 2021.01.11 |
| 백준 알고리즘 18353: 병사 배치하기(Python) (0) | 2020.12.21 |
| 백준 알고리즘 14501: 퇴사 (Python) (1) | 2020.12.19 |
| 백준 알고리즘 1932: 정수 삼각(Python) (0) | 2020.12.18 |