💬 문제 이해

K원을 만드는데 필요한 동전 개수의 최솟값 구하기

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

😀 처음 보고 든 생각

동전/거스름돈 류라고 해서 모두 그리디로 풀 수 있는건 아니다

그리디는 늘 최적해인지 검증해야한다!

검증

그리디로 해결 가능한 이유
가지고 있는 동전 중에서 큰 단위 = 항상 작은 단위의 배수.
그러므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

인풋의 작은 조건이 문제 푸는 방법을 좌우할 수 도 있구만
하여튼 그리디로 풀 수 있음 (=큰 수 부터 try)

👩🏻‍💻 1회차 코드

def calc_max_coin(coin, tmp) :
  num = 0
  while (tmp >= coin) :
    tmp -= coin
    num += 1
  return num

n, target = map(int, input().split())
coin_list = []
for _ in range (n) : coin_list.append(int(input()))

res = 0
tmp = target

# 큰 수부터  try
for i in range (n-1, 0, -1) :
  if coin_list[i] > tmp :
     continue
  else :
    coin_num = calc_max_coin(coin_list[i], tmp)
    if coin_num == 0 : 
      continue
    tmp -= coin_list[i] * coin_num
    res += coin_num
    coin_num = 0

print(res)

뭔가 이렇게 복잡한 문제가 아닌뎅 왤케 코드가 복잡해졌을까

타 블로그를 참고해서 겁나.ㅋㅋ..ㅋ... 훨씬 간단한 코드가 있다.

N, K = map(int, input().split()) 
coin_lst = list()
for i in range(N):
    coin_lst.append(int(input()))

count = 0
for i in reversed(range(N)):
    count += K//coin_lst[i] #카운트 값에 K를 동전으로 나눈 몫을 더해줌
    K = K%coin_lst[i] # K는 동전으로 나눈 나머지로 계속 반복

print(count)

정답!!

느낀점

아 구현.... 두줄따리 구현을 길게 돌아갔더니 현타가...
공부도 공부지만 구현도 많이 해보고 익히도록 노력하자