문제 링크

이 문제는 탐욕법으로 풀이하는 문제이다. 탐욕법으로 풀이 가능하다고 판단할 수 있었던 것은

(1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

문제의 위 문장 덕분이다.

탐욕법 적용이 가능한 이상 코드 자체는 어렵지 않다. 조건문만 잘 작성해주면 된다.

참, 가장 큰 값을 먼저 넣어보면서 대조해야하는데, 오름차순으로 정렬되어있기 때문에 reverse() 리스트 메서드를 이용해서 반전시킨 후 진행했다.

나의 풀이

N, K = map(int, input().split(" "))
mv = [] # 동전의 가치
count = 0 # 동전의 수

for i in range(N):
  mv.append(int(input())) # 동전 가치 저장

#  (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) greedy로 풀 수 있음.

mv.reverse() # 동전의 가치가 가장 큰 것이 맨 앞으로

for j in mv:
  if j <= K:  # K = 4200 j = 50000, 10000 ...
    if K % j == 0:
      count += K//j
      break
    else:
      count += (K//j)
      K = K % j
  else:
    continue

print(count)

강사님 풀이

N, K = map(int, input().split(" "))
coins = [] # 동전들
ans = 0 # 동전의 수

for i in range(N):
  coins.append(int(input())) # 동전 가치 저장

#  (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) greedy로 풀 수 있음.

coins.reverse() # 동전의 가치가 가장 큰 것이 맨 앞으로

for coin in coins:
  ans += K // coin #몫이 0이면 어차피 0이 더해지는구나, 그리고 K가 0이되면 마찬가지로 0이다.
  K = K % coin

print(ans)