본문 바로가기

알고리즘 (Python)/이것이 코딩 테스트다 with 파이썬

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

728x90
반응형

만들 수 없는 금액

난이도 : 下 풀이 시간 : 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까지의 모든 금액을 만들 수 있다'는 개념을 적용하여 구현하면 됩니다.
728x90
반응형