Baekjoon 11047번 동전 0

문제

https://www.acmicpc.net/problem/11047

걸린 시간

01 : 03 : 20

풀이

Python3

if __name__ == "__main__":
    N, K = map(int, input().split())    

    coin = []
    for _ in range(0, N):
        coin.append(int(input()))

    coin.sort(reverse=True)

    acc = 0
    count = 0
    for c in coin:
        q = (K-acc)//c
        if acc+c <= K:
            count += q
            acc += c*q

    print(count)

필요한 동전 개수의 최소값만 보고 BFS 로 접근했지만 구해야하는 금액의 범위가 1억까지기 때문에 다른 방법을 생각해야했다.

오름차순으로 주어진 동전의 종류들을 내림차순으로 재정렬하여 큰 금액의 동전부터 가능한 만큼 더하는 방법을 시도해 보았다.

"현재 금액에 동전을 더했을 때 목표 금액보다 작거나 같으면" 라는 조건에 참이면 반복문을 통해 연속해서 값을 누적시키는 방법을 사용했는데 가지고 있는 동전의 종류가 한개이고 1원이라면 1억번 이상 연산이 수행되어 시간초과가 난다. (문제의 시간제한 1초) 따라서 시간초과가 나지 않으려면 남은 금액을 동전으로 나눈 몫을 계산해서 한번에 더해야 한다.

문제의 유형이 그리디 알고리즘이라는걸 분류 목차를 보고 나서야 알았다. 그 전까지는 계속 그래프에 꽃혀 다른 방법을 생각하지 못했다. 문제에 사용할 수 있는 알고리즘의 폭을 넓게 생각해야겠다.