[Baekjoon] 백준 알고리즘 - 11047: 동전 0

1. 문제

www.acmicpc.net/problem/11047

11047번: 동전 0

2. 내가 생각했던 풀이과정

이 문제는 그리디이다. 그리디라고 생각한 이유는 입력받는 숫자의 단위의 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 돈을 종합해 다른 해가 나올수 없기 때문이다. 

또한, 그리디라고 힌트를 문제에서 주고 있는데 문제 풀이를 위한 최소한의 갯수를 사용하라고 했기 때문이다.

 

1) 단위의 갯수와, 돈을 입력받는다.

2) 입력받은 돈 단위를 큰 단위 순서(내림차순)으로 정렬한다

3) 정렬된 돈의 단위대로 배열을 돌면서 가장 큰 단위로 나누는데 이 때 나오는 몫이 사용하는 최소한의 동전의 갯수이다

4) 입력받은 돈과 나눈 단위로 나온 나머지는 다시 돈이 0원이 될 때까지 반복문을 돌려야하기 때문에 돈의 나머지는 다시 재정의 해준다.

5) 3번과 4번 과정을 돈이 0원이 될때까지 반복한다.

6) count를 마지막으로 출력해준다.

3. 나의 풀이

N, K = map(int, input().split())
count = 0
money_types = []

for i in range(N):
    money_types.append(int(input())) # 돈의 단위를 입력받는다

money_types.reverse() # 돈을 가장 큰 단위로 정렬한다 -> 그리디

for money in money_types:
    count += K // money
    K %= money

print(count)

4. 다른 사람의 풀이

다른 사람의 풀이도 원리가 매우 비슷하다.

5. 새로 알게된 점

그리디 알고리즘 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.