📖문제

• 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
• 동전을 적절히 사용해서 그 가치의 합을 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의 배수)

📘출력

• 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

📄내가 작성한 코드

import sys
input = sys.stdin.readline

N,K = map(int,input().split())
stack = []
count = 0
for i in range(N):
    A = int(input())
    stack.append(A)

for i in range(N):
    temp = stack.pop()

    if temp <= K:
        if K % temp == 0:
            count += int(K / temp)
            break
        else:
            count += int(K / temp)
            K = K % temp
print(count)

👉코드 설명

• 첫째줄에 동전의 종류 N, 가치의 합 K를 입력받는다.
• 둘째줄부터 동전의 가치 A를 입력받고 이를 스택에 넣는다.
• 동전의 가치 별로 비교하기 위해 스택에서 하나씩 꺼내어 temp변수에 저장한다.
• 스택에서 꺼낸값이 가치의 합보다 크면 그 다음 스택을 비교한다.
• 가치의 합을 스택에서 꺼낸값으로 나눴을때 나머지가 0이면 그 몫을 count에 더하고 반복문을 빠져나간다.
• 가치의 합을 스택에서 꺼낸값으로 나눴을때 나머지가 0이 아니면 몫은 count에 더하고, 나머지를 K값으로 한다.

❗❗Key Point

• 오름차순으로 동전의 가치를 입력받고, 비교시에는 제일 큰 수 부터 비교해야 가치의 합의 최솟값을 구할 수 있다. 즉, 나중에 넣은값을 가장먼저 비교해야 하므로 스택을 사용해야 한다는 것을 파악하는게 핵심이다.
• '구하려는 가치의 합>사용할 가치의 종류' 일 경우에만 비교한다.
• 딱 나눠떨어졌을때를 기준으로 놓고, 나누어 떨어지면 반복문 탈출, 나머지가 있으면 딱 나누어 떨어질때까지 다시 반복문을 돌도록 해야한다.

💢막혔던 부분

• 처음에 또 스택을 떠올리지 못해서 애를 먹었다. 안쓰고도 풀 수 있었을것 같은데 풀고보니 스택을 사용하는 편이 더 쉬웠을것 같았다.

😭후기

• 스택을 떠올리는데 좀 어려움이 있었지, 사용하고 나서는 막 그렇게 어렵지는 않았던거 같다.😄