[그리디 알고리즘] 만들 수 없는 금액 - 파이썬(python)

만들 수 없는 금액

난이도 : 下 풀이 시간 : 30분

시간 제한 : 1초 메모리 제한 : 128 MB

 

---

 

해답

 

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

result = 1

for i in unit:
    if result < i:
        break

    result = result + i

print(result)

---

예시

 

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)

---

해설

 

화폐 단위를 기준으로 오름차순으로 정렬한 뒤, 오름차순에 의하여 1부터 차례대로 특정한 금액을 만들 수 있는지 확인하여 답을 구하는 문제입니다.
result의 값이 존재할 때 '1부터 result-1까지의 모든 금액을 만들 수 있다'는 개념을 적용하여 구현하면 됩니다.