알고리즘 백준 11047 동전0(파이썬)

알고리즘 백준 11047 동전0(파이썬)

백준 동전0 파이썬

백준 파이썬 동전0 

 

 

문제

준규가 가지고 있는 동전은 총 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
#
# if __name__ == '__main__':
#
#     #N은 개수 K의 값의합
#     N,K = map(int, sys.stdin.readline().split())
#
#     coinList=[]
#     for i in range(N):
#         coin = int(sys.stdin.readline())
#         coinList.append(coin)
#
#     coinList.reverse()
#     #print(coinList)
#     count=0
#     for j in range(len(coinList)):
#         while True:
#             if K < coinList[j]:
#                 break
#             K -= coinList[j]
#             count+=1
#
#     print(count)

 

코드

import sys

if __name__ == '__main__':

    # N은 개수 K의 값의합
    N, K = map(int, sys.stdin.readline().split())

    coinList = []
    for i in range(N):
        coin = int(sys.stdin.readline())
        coinList.append(coin)

    coinList.reverse()         #1)
    # print(coinList)
    count = 0
    for j in range(len(coinList)):         #2)
        num = K//coinList[j]
        K -= coinList[j]*num
        count += num

    print(count)

 

 

문제설명

0) 그리디 알고리즘을 이용한 문제로서 가장 큰값을 우선적으로 생각해야한다

 

0-1) 위에 시간초과 코드는 while문을 사용하였는데 이 때문에 시간초과가 발생하였다

 

#1) 문제에서 주어진 코인이 낮은값부터 오므로 그리디 알고리즘에 맞게 역순해주었다

 

#2) 문제에서 주어진 큰 수부터 차례대로 K(맞춰야하는값)을 나누어 해당 값의 몫(나눠진횟수)을 구한 후
      

      그만큼 K값을 빼주고  count를 더해주었다!

 

 

깃허브

https://github.com/developer-hyun/Algorithm-Study/tree/main