그리디 문제 풀이 - 만들 수 없는 금액

🔸 만들 수 없는 금액

동전 n개가 주어졌을 때, 해당 동전들로 만들 수 없는 금액을 구하여라.

동전은 최대 1000개, 각 동전의 크기는 최대 1,000,000원이다.

ex) 1,2,3, 7원 동전이 주어졌을 때,

1원 : 1

2원 : 1

3원 : 3

4원 : 1+3

5원 : 2+3

6원 : 1+2+3

7원 : 7

8원 : 1+7

9원 : 2+7

10원 : 3+7

11원 : 1+3+7

12원 : 2+3+7

13원 : 1+2+3+7

14원 : X

📌 초기 접근 방법

처음에 생각한 접근 방식은 어려웠다.

1. 동전의 모든 조합을 구한다.
2. 조합 별 최종 합을 구한다.
3. 최종 합을 set에 담는다.

여기서 문제는 모든 조합을 구할 때 너무 많은 비용이 든다.

Combination 연산 시에는 팩토리얼 단위로 연산하기 때문이다.

📌 이후 접근 방법

만들 수 없는 금액의 조건은 두 가지라고 생각했다.

1. 가장 작은 동전보다 작은 금액
2. 모든 동전을 더한 것보다 큰 금액

따라서 오름차순 정렬을 수행한 뒤, 만들 수 없는 금액을 증가시켜나간다.

1. 오름차순 정렬 수행
2. 동전을 하나씩 꺼낸다.
3. 금액이 동전보다 작으면 stop
4. 금액이 동전보다 크면, 금액에 동전 값을 더한다.

소스코드

# Solution
def solution(data):
    target = 1
    for x in data:
        # 만들 수 없는 금액을 찾았을 때 반복 종료
        if target < x:
            break
        target += x

    # 만들 수 없는 금액 출력
    print(target)