[백준] 11047번 동전 0 - 결과 포함

www.acmicpc.net/problem/11047

11047번: 동전 0

그리디 알고리즘의 첫 문제이다.

그리디 알고리즘을 간단하게 말하면 현재 상황에서 가장 이득이 되는 결정을 하는 알고리즘이다.

미래에 대한 걱정은 하지 않고 현재 부딪힌 상황만 보고 판단하는 것이다.

 

이 문제는 주어진 돈의 종류를 최소한으로 써서 입력으로 들어오는 돈의 액수를 0으로 만드는 것이 목표이다.

 

우리가 거스름돈을 거슬러 줄 때를 생각하면 방법을 쉽게 찾을 수 있다.

예를 들어, 2500원짜리를 사고 10000원을 낸다면 거스름돈은 7500원이다.

이 때, 가장 적은 돈의 갯수를 위해서는 5000원 짜리 한 장, 1000원 짜리 두 장, 500원 짜리 한 장을 거슬러 줘야한다.

 

이와 같이 문제를 해결하면 된다.

주어지는 돈의 가치 리스트에서 가장 가치가 큰 돈부터 훑으면서 돈의 액수를 깎기 위해 시도하면 된다.

 

처음에는 단순하게 주어진 돈의 액수에서 돈의 가치만큼 계속해서 빼는 방법으로 해결했다.

주어진 테스트 케이스에서 출력은 문제가 없었지만 제출했을 때 시간 초과가 떴다.

 

만약 1원으로 1억을 채우기 위해서는 1억 번을 빼야하는 코드였던 것이다.

보통 시간 초과인 경우를 해결할 때는 이미 답이 나와있는 경우가 많았다.

즉, 일정한 규칙이나 패턴을 통해 반복문을 수행하지 않아도 답이 일정하게 나오는 경우에 시간을 대폭 단축시키는 경우가 많았다.

 

곱셈과 나눗셈을 이용해 시간 초과 문제를 해결했다.

10000원을 1000원으로 10번 빼는 것은 1000 X 10을 한 후 10000원에서 빼는 것이었다.

10번 반복하기 전에 10을 곱해서 한 번에 빼면 더 빠르게 해결할 수 있다.

 

결과적으로

최악의 경우 O(n^2)이었던 코드가 O(n)으로 바뀌었다.

 

[]

n, k = map(int, input().split())

data = list()
count = 0

for i in range(n):
    data.append(int(input()))

for num in reversed(data):
    if num > k:
        continue
    else:
        count += int(k / num)
        k -= (num * int(k / num))

print(count)