문제 04 : 만들 수 없는 금액(난이도 : 1/3)

1. 문제 설명

(1) 만들 수 없는 금액

• 편의점 점주는 N개의 동전을 가지고 있다.
• 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하시오.

(2) 입력 조건

• 첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어진다.(1 <= N <= 1,000)
• 둘째 줄에는 각 동전의 화폐단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
• 이 때, 각 화폐 단위는 1,000,000 이하의 자연수이다.

(3) 출력 조건

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

---

2. 문제 분석

• 코드 구현자체는 어려워 보이는 것이 없지면 설계과정에서 직관적으로 이해하기가 어려웠다.
• 문제 예시에서 N = 5이고, 각각 동전이 3원, 2원, 1원, 1원, 9원짜리 동전이라고 가정한다.
• 단순하게 사람의 직관을 이용하여 이 동전들의 조합을 만들면 다음과 같다.
• 만들 수 있는 양의 정수 금액의 리스트 = [1, 2, 3, 4, 5, 6, 7, 9, 10, 11, ....]
• 여기서 우리는 동전의 조합으로 8을 만들 수 없음을 알 수 있다.
• 그럼 이제 어떻게 8이 만들어 지지 않는지 컴퓨팅적 사고로 밝혀내야 한다.(결국, 나는 밝혀내지 못 해서 문제풀이 해설을 참고했다....)
• 풀이 해설에서는 하나의 변수에 화폐를 작은 순으로 더해가면서 그 값이 다음 더해야 할 화폐의 값보다 작으면 만들 수 없다고 설명한다.

 

• 맨 처음 변수(이후, target)는 1로 초기화한다.(만들 수 없는 양의 정수를 찾아야 하니 그 최솟값인 1로 초기화한다.)
• 동전을 단위가 작은 순서부터 오름차순으로 정렬하여 각각 target에 그 값을 더한다.
• 위의 예시인 coin = [1, 1, 2, 3, 9]를 토대로 설명하면 다음과 같이 진행된다.
• 먼저, target의 초기값의 1은 coin[0] = 1과 값이 같으니 만들 수 있는 정수가 된다.
• 따라서 target += coin[0]을 실행한다.(target = 2)
• 그리고 target과 coin[1]을 비교한다.
• target(=2) > coin[1](=1) 이므로 2 역시 만들 수 있는 정수가 되며 마찬가지로 target에 coin[1]의 값을 더한다.

 

• 그렇게 target에 coin[2]와 coin[3]의 값을 더할 수 있게 되고 결과적으로 target의 값은 8이 된다.
• 그런데 target(=8) < coin[4](=9)이므로 target의 값인 8은 만들 수 없는 정수가 된다.
• 따라서 반복을 멈추고 target의 값인 8을 출력하면 정답이 된다.

 

• 해설을 보니 어렴풋이 왜 8을 만들 수 없는지 이해는 되는데 직관적이고 뚜렷하게 이해하기는 어려웠다.
• 내가 이해한 바로는 다음과 같다.
• taget의 값이 다음 값과 같거다 더 큰 경우 taget은 그 이전의 동전의 조합들로 만들 수 있는 값이다.
• 왜냐하면, target에는 동전의 작은 값들부터 합이 누적되었기 때문이다.
• 예시된 상황에서 target의 값은 [1, 2, 3, 5, 8, ...]이 된다.
• target[i]의 값보다 작거나 같은 숫자들은 coin[0]부터 coin[i]까지의 조합으로 만들 수 있다.
• 그리고 target이 다음 값과 값이 같으면(target[i+1] == coin[i+1]) target은 다음 동전 하나(coin[i+1])만으로 만들 수 있는 값이다.
• 이제 문제는 다음 동전의 값이 누적된 target보다 다음에 더해야할 동전의 값이 더 클 때 발생한다.
• target = 8인 상황에서 우리는 이전에 나온 모든 동전을 소모하였는데, 위의 설명에 따라 다음 동전에 따라 동전의 조합으로 1~8원을 만들 수 있다고 생각하게 된다.
• 그러나 아직까지 해당 조합으로 만들 수 있는 최대 값은 7이 된다.
• 그래서 나머지 동전의 조합으로 8을 만들기 위해서는 다음 동전이 6~8원의 가치를 가지고 있을 때 가능하다.
• 하지만 예시에서 다음 더해야 할 동전의 값어치는 9원으로 8은 만들 수 없게 된다.
• 따라서, 8은 예시의 동전 조합을 만들 수 없는 최솟값이 된다.

 

• 다른 예시를 살펴보자. N = 3이고 coin = [3, 5, 7]일 때 처음부터 target(=1) < coin[0](=3)인 상황이 발생하여 이 동전의 조합으로는 1을 절대 만들 수 없다는 사실을 알 수 있다.

---

3. 코드 구현 - 문제 풀이 해설 방법

# 동전 갯수 입력
n = int(input())

# 화폐 단위 입력
coin_list = list(map(int, input().split()))

# 화폐를 크기가 작은 순부터 오름차순 정렬
coin_list.sort()

### 정답 해설 방법 ###

target = 1 # 해당 변수에 화폐를 작은 순 부터 더해 해당 값이 다음 화폐보다 작으면 만들 수 없는 값이 된다.
for x in coin_list:
    # 만들 수 없는 금액을 찾았을 때 반복 종료
    if target < x:
        break
    target += x

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

• 문제 분석만 성공했다면 코드 구현자체는 정말 쉽다.
• 알고보면 쉬운데 왜 이런 생각을 하지 못 했을까하는 아쉬움이 남는다.

---

4. 후기

  내가 평소에 직관적으로 생각하는 버릇이 있는데 이 문제에서 굉장히 큰 난항을 겪었다. 내가 분석한 방법으로 설명을 적어 놓았지만 사실 명쾌하게 만족스럽지는 않다. 이럴 때 쓰는 방법은 그냥 그대로 외우는 방법이 있긴 한데, 이런 문제가 과연 코딩 테스트 문제에서 나올까 의문스럽기도 하다. 그래도 혹시 발생할 수 있는 상황에 대해서 이 자료를 참고자료로 사용할 수 있도록 하면 그 의미가 그나마 생기리라 기대한다.

---

github : Algorithms/q4_0.py at main · LeeSeok-Jun/Algorithms (github.com)

LeeSeok-Jun/Algorithms