[PART3] 4. 만들 수 없는 금액 ❗

코뉴·2021년 1월 3일

이코테: 문제풀이

목록 보기

8/28

알고리즘 유형별 기출문제: 그리디

💻 4. 만들 수 없는 금액

난이도🖤🤍🤍 | 풀이시간 30분 | 제한시간 1초 | 메모리제한 128MB | K대회 기출

📌2021/01/03 작성 코드

# 입력
n = int(input())
data = list(map(int, input().split()))
data.sort(reverse=True) # 내림차순으로 정렬

# 알고리즘
ret = 1 # 1로 초기화
stop = False
while not stop:
    temp = ret # temp에 ret 값 할당

    # 내림차순으로 정렬된 data 순회하면서 ret값 만들 수 있는지 확인
    for x in data:
        if temp//x > 0: # 몫이 0보다 크면
            temp -= x # 그 값을 temp에서 뺀다
        else:
            continue
    # temp가 0이라면 ret값 만들 수 있다는 것
    if temp == 0:
        ret += 1 # 다음 테스트를 위해 + 1
    else:
        stop = True

# 출력
print(ret)

💭 아이디어

알고리즘을 짰지만 왜인지 확신이 들지 않는다...!

🤓 문제 해설

01

이 문제는 정렬을 이용한 그리디 알고리즘으로 해결할 수 있는 문제이다. 문제 해결을 위한 정확한 아이디어를 떠올리기 위해서는 충분히 고민을 해야 하는 문제이므로, 그리디 알고리즘에 익숙하지 않은 독자라면 문제 해결이 쉽지 않을 수 있다.

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

기본적으로 그리디 알고리즘은, 현재 상태에서 매번 가장 좋아보이는 것만을 선택하는 알고리즘이라고 하였다. 구체적으로 현재 상태를 '1부터 target-1까지의 모든 금액을 만들 수 있는 상태'라고 보자. 이때 매번 target인 금액도 만들 수 있는지(현재 확인하는 동전의 단위가 target 이하인지) 체크하는 것이다. 만약 해당 금액을 만들 수 있다면, target의 값을 업데이트 (현재 상태를 업데이트) 하면 된다.

02

예를 들어 3개의 동전이 있고, 각 화폐의 단위가 1, 2, 3이라고 하자.
그러면 1부터 6까지의 모든 금액을 만들 수 있다.

1원: 1
2원: 2
3원: 3
4원: 1 + 3
5원: 2 + 3
6원: 1 + 2 + 3

그 다음 우리는 금액 7도 만들 수 있는지 확인을 하면 된다. 이때 화폐 단위가 5인 동전 하나가 새롭게 주어졌다고 가정하자. 이제 화폐 단위가 5인 동전이 주어졌기 때문에, 1부터 11까지의 모든 금액을 만들 수 있다. 당연히 금액 7도 만들 수 있다는 것이 자동으로 성립한다.

1원: 1
2원: 2
3원: 3
4원: 1 + 3
5원: 5
6원: 5 + 1
7원: 5 + 2
8원: 5 + 3
9원: 5 + 3 + 1
10원: 2 + 3 + 5
11원: 1 + 2 + 3 + 5

이후에 우리는 금액 12도 만들 수 있는지 확인을 하면 되는 방식이다. 이때 화폐 단위가 13인 동전 하나가 새롭게 주어졌다고 가정하자. 이때 금액 12를 만드는 방법은 존재하지 않는다. 그래서 이 경우에는 정답이 12가 된다.

03

이제 또 다른 예시를 확인해보자. 이번에는 문제를 해결하는 과정을 단계별로 보이겠다. 만약에 동전을 4개 가지고 있고, 화폐 단위가 각각 1, 2, 3, 8이라고 해보자.

1. 처음에는 금액 1을 만들 수 있는지 확인하기 위해, target = 1로 설정한다.
1. target = 1을 만족할 수 있는지 확인한다. 우리에게는 화폐 단위가 1인 동전이 있다. 우리는 이 동전을 이용해서 금액 1을 만들 수 있다. 이어서 target = 1 + 1 = 2로 업데이트를 한다. (1까지의 모든 금액을 만들 수 있다는 말과 같다)
1. target = 2를 만족할 수 있는지 확인한다. 우리에게는 화폐 단위가 2인 동전이 있다. 따라서 target = 2 + 2 = 4가 된다. (3까지의 모든 금액을 만들 수 있다는 말과 같다)
1. target = 4를 만족할 수 있는지 확인한다. 우리에게는 화폐단위가 3인 동전이 있다. 따라서 target = 4 + 3 = 7이 된다. (6까지의 모든 금액을 만들 수 있다는 말과 같다)
1. target = 7을 만족할 수 있는지 확인한다. 우리에게는 이보다 큰, 화폐 단위가 8인 동전이 있다. 따라서 금액 7을 만드는 방법은 없다. 따라서 정답은 7이 된다.

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

04

이 문제는 그리디 알고리즘 유형의 문제를 여러 번 풀어보았다면 풀이 방법을 떠올릴 수 있지만, 그리디 알고리즘이 익숙하지 않다면 쉽게 이해되지 않을 수 있는 문제이다. 따라서 이 문제가 어렵다면 그리디 알고리즘 유형의 문제를 더욱 많이 접해보자.

참고로 이 문제는 앞서 이론 파트에서 다루었던 '거스름돈' 문제와는 다른 문제이다. 거스름돈 문제는 각 화폐 단위마다 무한 개의 동전이 존재한다고 가정했는데, 여기서는 동전의 수가 한정적이라는 점이 다르다.

🤓 답안 예시

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)

🤔 리뷰

어려웠다.
해설은 어렴풋이 이해가 됐지만 내가 짠 알고리즘이 최종적으로 맞았는지 틀렸는지는 잘 검증이 안된다...
나름대로 이해해 보고자 노력해 본 흔적이 아래에.
target이 의미하는 바는 '다음 동전까지 고려한다면 최소 이 금액은 만들 수 있다!' 는 뜻이었다. 동전들이 오름차순으로 정렬되어 있다고 가정하므로, i번째 동전 다음에 오는 i+1번째 동전은 i번째 동전의 가치와 같거나 클 것이기 때문이다. 그래서 target에 current value를 더해주는 것이다.
따라서 첫번째 동전부터 i+1번째 동전까지의 합은 최소 target은 되겠지~ 라는 가정과 함께 i+1번째 동전의 current value를 본다. 이 때, current value가 target보다 크다면 아무리 더해도 target을 만들 수 없다. 즉, 만들 수 없는 최소 금액이 된다.