04_만들 수 없는 금액

동빈이는 N개의 동전을 가지고 있다.

이 때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성해라.

 

예를 들어 N=5이고, 각 동전이 각각 3, 2, 1, 1, 9원이라고 하면 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원이다.

---

문제의 시간제한이 1초이고, 동전의 개수가 1000개 이하이므로 O(N^2)도 되겠구나 라는 생각을 했다.

그리고 동전의 단위도 1,000,000이하의 자연수라서 동전의 단위로 반복문을 돈다면 O(NlogN)도 가능하겠다는 생각을 했다.

처음에는 동전들을 오름차순 정렬해서 1부터 가장 큰 동전의 값까지 반복문을 돌려서 1 ~ 동전의 최댓값까지 동전을 만들 수 있는 경우를 확인해보려고 했다.

하지만 그럴 경우 동전의 단위가 서로 나눠떨어지지 않으므로 그리디 알고리즘으로 구할 수 없다.

그래서 고민하다가 결국 풀이를 봤다.

 

이 문제는 정렬을 활용한 그리디 알고리즘으로 풀 수 있는 문제이다.

일단 동전에 대한 정보가 주어졌을 때, 화폐 단위를 기준으로 오름차순 정렬한다. 그리고 1부터 차례대로 특정한 금액을 만들 수 있는지 확인하면 된다.

 

1부터 target - 1까지 모든 금액을 만들 수 있다고 가정해보자.

우리는 화폐 단위가 작은 순서대로 동전을 확인하며, 현재 확인하는 동전을 이용해 target 금액 또한 만들 수 있는지 확인하면 된다.

만약 target 금액을 만들 수 있는 경우 target 값을 증가시킨다.

 

예를 들어 5개의 동전이 있고, 각 동전은 1, 2, 3, 5, 13원이라고 가정해보자.

 

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

2. target = 1을 만족시킬 수 있는지 확인한다.

    우리는 1원짜리 동전이 있으므로 만들 수 있다. (target=1 >= x=1)

    그러므로 target = 1 + 1 = 2로 업데이트한다.(1까지의 모든 금액을 만들 수 있다는 뜻)

    1원 = 1

3. target = 2를 만족시킬 수 있는지 확인한다.

    우리는 2원짜리 동전이 있으므로 만들 수 있다.(target=2 >= x=2)

    그러므로 target = 2 + 2 = 4로 업데이트한다. (3까지의 모든 금액을 만들 수 있다는 뜻)

    1원 = 1

    2원 = 2

    3원 = 1 + 2

4. target = 4를 만족시킬 수 있는지 확인한다.

    우리는 3원짜리 동전이 있으므로 만들 수 있다. (target=4 >= x=3)

    그러므로 target = 4 + 3 = 7으로 업데이트한다. (6까지의 모든 금액을 만들 수 있다는 뜻)

    1원 = 1

    2원 = 2

    3원 = 1 + 2

    4원 = 1 + 3

    5원 = 2 + 3

    6원 = 1 + 2 + 3

5. target = 7을 만족시킬 수 있는지 확인한다.

    우리는 5원짜리 동전이 있으므로 만들 수 있다. (target=7 >= x=5)

    그러므로 target = 7+ 5 = 12으로 업데이트한다. (11까지의 모든 금액을 만들 수 있다는 뜻)

    1원 = 1

    2원 = 2

    3원 = 1 + 2

    4원 = 1 + 3

    5원 = 2 + 3

    6원 = 1 + 2 + 3

    7원 = 2 + 5

    8원 = 1 + 2 + 5

    9원 = 1 + 3 + 5

    10원 = 2 + 3 + 5

    11원 = 1 + 2 + 3 + 5

5. target = 12을 만족시킬 수 있는지 확인한다.

    우리는 이보다 큰 13원짜리 동전이 있으므로 금액 12를 만드는 방법은 없다. (target=12 < x=13)

    따라서 정답은 12이다.

 

풀이 코드

# Q_04_만들 수 없는 금액
n = int(input())
coins = list(map(int, input().split()))
coins.sort() # 오름차순 정렬

target = 1
for x in coins:
    # 만들 수 없는 금액을 찾았을 때 반복 종료
    if target < x:
        break
    target += x

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

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

 

좀 더 그리디 알고리즘에 익숙해져야겠다.

문제 풀이가 잘 생각나지 않는다.