백준 11047번- '동전 0' (PYTHON 풀이)

문제:

 

사용자로부터 동전 종류의 개수와 원하는 값을 입력받는다. 이후 동전 종류의 개수만큼 동전의 종류를 전부 입력받고 이 동전을 조합해서 최소한으로 원하는 값을 만들 수 있는 횟수를 구하면 된다.

이전에 비슷한 문제 유형이 있던 것 같으니 참고하길 바란다.

 

풀이:

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

for i in range(N):
    value.append(int(input()))
value.sort(reverse=True)

for j in value:
    if j <= K:
        co = K // j
        count += co
        K %= j

print(count)

답은 다음과 같다. 일단 필자는 동전 종류를 전부 리스트에 보관하고 정렬해서 높은 수를 먼저 오게 내림차순으로 정리하였다.

그 이유는 큰 수를 기준으로 빼줘야 최소한으로 개수를 카운트할 수 있기 때문이다.

 

이후 반복문과 조건문을 통해 모든 동전의 종류를 하나씩 돌면서, 우리가 계산하고자 하는 값과 동전 종류의 값을 비교해서 계산하고자 하는 값이 더 크다면 해당 값을 동전 종류만큼 나눠준다. 그 다음 그 몫을 카운트에 더해준다. 이 과정을 진행하게 되면 최소한으로 해당 동전의 종류만큼 계산할 수 있는 횟수를 전부 구하게 되고 이를 카운트에 더하게 된다.

예를 들어 계산을 원하는 값이 1200원이고 동전 종류가 100원이라면, 1220//100으로 계산되어 몫이 12가 나올 것이다. 그 값만큼 횟수를 세어줘야 하니 count에 담는 것이다.

그 다음 100으로 더 이상 나눠떨어지지 않는 나머지는 또 현재 동전의 종류보다 더 낮은 금액의 동전의 종류로 계산을 해줘야하니 나머지를 구해서 K의 값을 갱신하다. 앞선 예시에 이어서 설명하자면 1220%100 이므로 K는 20이 되니까 그 다음 순서의 동전 종류로 추가 계산을 해준다.

이 과정을 전부 진행하게 되면 모든 동전 종류를 반복하며 횟수를 계산하게 될 것이고 최종으로 전부 더해진 이 횟수를 출력하면 문제를 풀 수 있다!