★그리디알고리즘★ 동전 0 [백준 파이썬 11047번]

그리디 알고리즘의 정당성

그리디 알고리즘으로 최적해를 도출하기 위해서는 아래 두가지 조건을 만족해야 한다.

1.탐욕적 선택 속성 (greedy choice property)
탐욕적인 선택이 항상 안전하다는 것이 보장된다는 의미이다. 즉, 그리디한 선택이 언제나 최적해를 보장해야한다.

2. 최적 부분 구조 (optimal substructure)
부분 최적해(Local optimum)들이 모여 전체 최적해(Global optimum)를 구할 수 있는 경우이다. 즉, 전체 문제가 여러 부분 문제로 분할되며, 이 단계 하나하나에 대한 최적해가 도출되어야 한다는 의미이다.

 

import sys

A = list(map(int, sys.stdin.readline().split(' ')))
B=[]
for i in range(A[0]):
    b = int(sys.stdin.readline())
    B.append(b)
won = A[1]
cnt = 0
for i in range(len(B)-1,-1,-1):
    #print(B[i])
    c = won//B[i] #4200//1000 = 4 200//100 = 2
    won = won- B[i]*c #4200 - 4*1000 = 200
    cnt+= c
print(cnt)