문제
N개의 동전을 사용해 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램
유형 분석
최솟값을 구하며 딱히 다른 알고리즘이 생각나지 않는다.
아이디어
주어진 숫자리스트를 작은 순서대로부터 확인을 하면서
만들 수 있는 금액 체크 여부를 1부터 시작해서 차근차근 가능한지 확인한다.
과정은 다음과 같다.
1원을 만들 수 있는가? -> 1원이 있어야만 한다. -> 없다면 종료, 있다면 현재 만들 수 있는 최대 금액은 1원디다.
2원을 만들 수 있는가? -> 1원 또는 2원이 있어야만 한다. -> 없다면 종료, 있다면 현재 만들 수 있는 최대 금액은 3원, 4원디다.
...
이런식의 아이디어를 갖는다.
예를 들어, [1, 1, 4, 5, 6]
작은거 부터 확인해보면,
1원으로 1원까지 만들 수 있다.
1원으로 2원까지 만들 수 있다.
4원으로 3원을 만들 수 있다. -> 3원 종료
구현
1. 리스트를 오름차순으로 정렬
2. 확인금액(target)을 1로 한다.
3. 리스트를 하나씩 꺼내서 확인 금액(target)이 꺼낸 금액보다 작으면 종료
4. 만약 확인하려는 금액이 크면 확인 금액(target) += 꺼낸 금액
코드
num = map(int, input("입력 : "))
num.sort()
target = 1
for i in num:
if target < i:
break
target += i
print(target)
