개발하는데 다 이유가 있겠지

[Silver IV] 동전 0 - 11047

문제 링크

성능 요약

메모리: 31120 KB, 시간: 40 ms

분류

그리디 알고리즘

제출 일자

2024년 2월 20일 17:22:18

문제 설명

준규가 가지고 있는 동전은 총 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


def solution():
    left_money = 0
    count = 0
    coins = []

    N, K = map(int, input().split())
    for i in range(N):
        A = int(input())
        # K 보다 같거나 작은 동전들만 리스트에 추가
        if A <= K:
            coins.append(A)

    for j in range(len(coins)):
        if max(coins) <= K:
            left_money = K % max(coins)
            count += K//max(coins)
            coins.remove(max(coins))
            K = left_money
        elif max(coins) > K:
            coins.remove(max(coins))
        elif left_money == 0:
            return

    print(count)


solution()

 

너무 비효율적이게 푼 느낌이 있어서 찾다보니 `그리디 알고리즘`이라는 방법이 있었다.

 

---

그리디 알고리즘(Greedy Algorithm)

그리디 알고리즘(탐욕법, 욕심쟁이 알고리즘)이란?

• "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법
  그리디 알고리즘
• 이러한 방법을 이용해 최적의 해를 구할 수 있는지 검토한다.
• 그리디를 이용하여 최적의 해가 되는지 추론해서 적절히 사용해야 한다.

조건

• 가지고 있는 동전 중 큰 단위가, 항상 작은 단위의 배수라면, 작은 단위의 동전을 종합해 다른 해가 나올 수 없기 때문에 그리디 알고리즘이 가능하다.
• 가장 큰 동전단위 단위부터 시작하여 계산하면 필요한 동전 개수의 최솟값을 구할 수 있다.(내림차순 정렬)
• 동전의 종류가 N개일때, 시간 복잡도는 O(n^2)이다.
  (동전의 종류만큼 진행)

def solution():
    coins = []
    count = 0

    N, K = map(int, input().split())

    # N개만큼 동전의 가치 입력
    for i in range(N):
        coins.append(int(input()))

     # 내림차순 정렬
    coins.sort(reverse=True)

    for j in coins:
        # 필요한 코인수 count
        count = count + (K//j)
        # 나머지 돈
        K = K % j  
        if (K <= 0):
            break

    print(count)

solution()

 

❗️그리디 알고리즘은 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출할 수 있는지 검토가 가장 중요한 것 같다.