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

- 입력 조건

첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어집니다. (1<=N<=1,000)

둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분합니다. 이때, 각 화폐 단위는 1,000,000 이하의 자연수입니다.

- 출력 조건

첫째 줄에 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력합니다.

 

* 방법1

아이디어: 정렬을 이용한 그리디 알고리즘

동전에 대한 정보가 주어졌을 때, 화폐 단위를 기준으로 오름차순 정렬한다. 이후에 1부터 특정한 금액을 만들 수 있는지 확인한다. 1부터 target-1 까지의 모든 금액을 만들 수 있다고 가정해보자. 화폐 단위가 작은 순서대로 동전을 확인하며, 현재 확인하는 동전을 이용해 target 금액 또한 만들 수 있는지 확인하면 된다. 만약 target 금액을 만들 수 있다면, target 값을 업데이트하는(증가시키는) 방식을 이용한다.

 

기본적으로 그리디 알고리즘은, 현재 상태에서 매번 가장 좋아보이는 것만을 선택하는 알고리즘

구체적으로 현재 상태를 'target-1 까지의 모든 금액을 만들 수 있는 상태'라고 보자. 이때 매번 target인 금액도 만들 수 있는지(현재 확인하는 동전의 단위가 target 이하인지) 체크하는 것이다. 만약 해당 금액을 만들 수 있다면, target의 값을 업데이트(현재 상태를 업데이트)하면 된다.

 

(예시) 동전의 개수 N=4, 화폐 단위가 1, 2, 3, 8인 경우

(0) 처음에는 금액 1을 만들 수 있는지 확인하기 위해 target=1로 설정 

(1) target=1을 만족할 수 있는지 확인 → 만들 수 있으므로 target=2 (1+1)로 업데이트 

(1까지의 모든 금액을 만들 수 있다는 말과 같음)

(2) target=2를 만족할 수 있는지 확인 → 화폐 단위가 2인 동전이 있으므로 target=4 (2+2)로 업데이트

(3까지의 모든 금액을 만들 수 있다는 말과 같음)

(3) target=4를 만족할 수 있는지 확인 → 화폐 단위가 3인 동전이 있으므로 target=7 (4+3)로 업데이트

(6까지의 모든 금액을 만들 수 있다는 말과 같음)

(4) target=7을 만족할 수 있는지 확인 → 7보다 큰 화폐 단위가 8인 동전이 있음

따라서 금액 7을 만드는 방법은 없음 (정답은 7)

 

이러한 원리를 이용하면, 단순히 동전을 화폐 단위 기준으로 정렬한 뒤에, 화폐 단위가 작은 동전부터 하나씩 확인하면서 target 변수를 업데이트하는 방법으로 최적의 해를 계산할 수 있음

 

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)

 

 

 

github.com/501501/codingTest/commit/64e6404e13a87490a5d4c31f3c1e3f4c990c80e2

#11-04 · 501501/codingTest@64e6404