[그리디] 04 만들 수 없는 금액

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

---

사고 과정

• ex) 3 2 1 1 9
• 동전을 오름차순으로 정렬한다. 1 1 2 3 9

• 동전 1원을 가지고 있다면 1원을 만들 수 있다. target = 1

  ⇒ 1원으로 1원까지 만들 수 있다. [1]

• 그 다음 숫자 2원을 만들 수 있는지 확인한다. target = 1+1

  ⇒ 1원 추가로 1(1), 2(1+1)원까지 만들 수 있다. [1, 1]

• 그 다음 숫자 3원을 만들 수 있는지 확인한다. target = 1+1+1

  ⇒ 2원 추가로 3(1+2), 4(1+1+2)원까지 만들 수 있다. [1, 1, 2]

• 그 다음 숫자 5원을 만들 수 있는지 확인한다. target = 1+1+1+2

  ⇒ 3원 추가로 5(1+1+3), 6(1+2+3), 7(1+1+2+3)원까지 만들 수 있다.

• 그 다음 숫자 8원을 만들 수 있는지 확인한다. target = 1+1+1+2+3

  ⇒ 9원 추가로 8원을 만들 수 없다

  ⇒ 9원을 추가하면 9(9), 10(1+9), 11(1+1+9), 12(1+2+9), 13(1+1+2+9), 14(1+1+3+9), 15(1+2+3+9), 16(1+1+2+3+9)원을 만들 수 있다.

---

풀이

나의 코드

import itertools

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

# 작은 수가 앞에 오도록 정렬
coin.sort()  # 1 1 2 3 9

f = False
# 양의 정수 금액이므로 1부터 만들어본다.
for i in range(1, max(coin) + 2):
  if i in coin:
    continue
  # 동전 리스트에 없다면 조합해서 4가 되는지 확인

  # 4보다 작은 수 찾기
  for j in coin:
    # if 합이 4보다 작으면 정답
    if j > i:
      m_idx = coin.index(j) - 1
      break
  print('hi')
  print(m_idx)
  # 모든 조합 중에서 4가 있으면 다음 정수로
  for l in range(2, m_idx + 2):
    print(f'target {i}, {l}개 조합')
    for k in list(itertools.combinations(coin[: m_idx + 1], l)):
      print(k,sum(k))
      if sum(k) == i:
        f = True
        print('middle',i)
        break
    if f:
      break
  if f:
    print('go to next')
    f = False
    continue 
  print('result',i)
  break

정말 복잡하게 풀었다..

책 코드를 보고 수정을 했다.

책의 코드

# 수정된 코드
n = int(input())
coin = list(map(int, input().split()))
coin.sort()
target = 1
for c in coin:
  if c <= target:
    target += c
  else:
    print(target)

---

💡사고 과정 흐름을 공식화하자

• 주어진 숫자로 조합할 수 있는 수를 구할 때는

  앞의 수에 현재 가지고 있는 수를 더해서 계산하자

  ex) 숫자 2와 3을 가지고 있으면 2, 3, 2+3를 만들 수 있고

  새로운 숫자 5가 생기면 5, 2+5, 3+5, 2+3+5 를 만들 수 있다.