[이코테] 그리디 문제 : Q 04. 만들 수 없는 금액

문제

동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 좋 최솟값을 구하는 프로그램을 작성하세요.

예를 들어, N = 5이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리 (화페 단위) 동전이라고 가정합시다. 이패 동빈이가 만들 수 없는 양의 정수 금액 중 최초값은 8원입니다.

또 다른 예시로, N = 3이고, 각 동전이 각각 3원, 5원, 7원짜리 (화페 단위) 동전이라고 가정합시다. 이태 동빈이가 만들 수 없는 양의 정수 금액 충 최초값은 1원입니다.

 

입력 조건

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

출력 조건

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

 

입력 예시

5

3 2 1 1 9

출력 예시

8

 

---

<내 풀이>

어렵다.

현재 가지고 있는 코인들을 조합해서 나올 수 있는 숫자를 모두 새로운 리스트에 넣는다. 예를 들어 3 2 1 1 9가 있다고 가정하면, 우선 3 2 1 1 9를 새로운 리스트에 넣고, 이 5개의 코인 중에서 2개를 더해서 나올 수 있는 결과들 '어쩌구, 저쩌구, ...., '를 모두 새로운 리스트에 넣는다. 3개를 더해서, 4개를 더해서, 5개 모두 더해서 나올 수 있는 결과들도 모두 리스트에 넣는다. 이 리스트 안에 있는 수들은 중복이 되어 있을 것이기 때문에 set()을 사용해서 중복 수를 제거한다. 

while 루프를 돌면서 이렇게 새로 만들어진 set에 존재하지 않는 가장 작은 양의 정수를 구한다.

좀 비효율적인 것 같다. 너무 계산할 것들이 많은 것 같다.

 

itertools 라이브러리를 찾았다. 이 라이브러리에 있는 combination을 활용해서 코드를 짰다.

from itertools import combinations as comb

coins = [3, 2, 1, 1, 9]

list2 = list(comb(coins, 2))
print(list2)

list3 = list(comb(coins, 3))
print(list3)

list4 = list(comb(coins, 4))
print(list4)

결과는 다음과 같이 2개, 3개, 4개의 원소로 구성된 튜플로 이루어진 리스트가 출력된다.

우리가 얻고 싶은 것은 튜플 각각을 더한 값이다. 

 

그 값을 얻을 수 있게 코드를 짜줬다. 근데 이건 너무 긴 것 같다.. 

from itertools import combinations as comb

coins = [3, 2, 1, 1, 9]

list2 = list(comb(coins, 2))
print(list2)

# 튜플 안에 있는 원소를 더한 값을 새 리스트에 저장
new_list = []
for i in list2:
  new_list.append(sum(i))

print(new_list)

 

결과는 얻었다. 하지만 코드를 좀 간단하게 만들고 싶다. 이건 나중에 찾아보고 일단 문제를 풀어보자.

 

<코드>

from itertools import combinations as comb

n = int(input())
coins = list(map(int, input().split()))

all_sum = [i for i in coins]

for i in range(2, len(coins)):
  new_list = list(comb(coins, i))
  # 튜플 안에 있는 원소를 더한 값을 새 리스트에 저장
  for j in new_list:
    all_sum.append(sum(j))

# 중복 제거 위해서 리스트를 set으로 만듦.
set(all_sum)

# 1부터 all_sum 안에 존재하는지 확인
number = 1
while True:
  if number not in all_sum:
    break
  number += 1

print(number)

 

 

<책 풀이>

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)

사실 책의 풀이가 이해되지 않는다. 책에는 그리디 알고리즘이 익숙하지 않다면 이해되지 않을 수 있는 문제라고 적혀있다. 그리디 알고리즘 문제를 더 많이 풀어봐야겠다. 나중엔 이해가 되겠지!

 

일단 책의 설명은 다음과 같다.

동전을 오름차순 정렬한다. 이후에 1부터 차례대로 특정한 금액을 만들 수 있는지 확인한다.

예를 들어 1, 2, 3, 8 동전이 있다고 가정하자.

1. 우선 1을 만들 수 있는지 확인하기 위해 target = 1로 설정한다.
2. 동전 1이 있기 때문에 target을 만들 수 있다. target = 1 + 1 = 2로 업데이트한다. (1까지 모든 금액을 만들 수 있다는 뜻)
3. target = 2를 만들 수 있는지 확인한다. 동전 2가 있기 때문에 target을 만들 수 있다. target = 2 + 2 = 4로 업데이트한다. (3까지 모든 금액을 만들 수 있다는 뜻)
4. target = 4를 만들 수 있는지 확인한다. 동전 3이 있기 때문에 target을 만들 수 있다. target = 4 + 3 = 7로 업데이트한다. (6까지 모든 금액을 만들 수 있다는 뜻)
5. target = 7을 만들 수 있는지 확인한다. 동전 8이 있다. 따라서 7을 만들 수 있다. 정답은 7이다.