[수행 과정] 1) 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해 선택 2) 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사 3) 해 검사 : 현재까지 선택한 해 집합이 문제를 해결할 수 있는지 검사 → 전체 문제를 해결하지 못한다면 1)로 돌아가 다시 수행
# 백준 11047번 : 동전 개수의 최솟값 구하기
# 가장 기본적인 그리디 문제
N,K = map(int,input().split())
A = [0] * N
# 데이터 삽입
for i in range(N):
A[i] = int(input())
count = 0
# 큰 동전부터 선택하면서 K원 만들기
for i in range(1,N+1):
now_max = A[-i]
if now_max <= K:
# 몫은 동전 개수에 해당
count += int(K // now_max)
# 나머지는 나머지 금액에 해당
K = K % now_max
print(count)
# [그리디 알고리즘에서 자주 사용하는 우선순위 큐]
# 현재 상황에서 최선의 선택을 반복하기 때문에 우선순위 큐를 사용하여 문제를 해결하는 경우 흔함
# 구현 방식 1) PriorityQueue
from queue import PriorityQueue
myque = PriorityQueue
# 기본 함수
put(data) # 원소 추가
get() # 큐에서 데이터 꺼내기
qsize() # 큐 사이즈 가져오기
empty() # 큐가 비어 있는지 확인
# 구현 방식 2) heapq
import heapq
mylist = []
heapq.heappush(mylist, 1)
# 기본 함수
heappush(mylist, data) # data를 list(heap 자료구조) 형태로 저장
heappop(mylist) # list(heap 자료구조)에서 데이터 꺼내기
heapify(mylist) # 일반적인 list를 heap 자료구조로 변환
# 이차원 리스트의 정렬 방식은 데이터 입력 순서를 통하여 조정할 수 있음
# 백준 1931 문제
# 데이터 삽입 : 끝나는 시간을 기준으로 정렬하고 같다면 시작 시간을 기준으로 정렬
# 정렬을 위해 끝나는 시간을 0번째에 삽입
for i in range(N):
s,e = map(int,input().split())
time_list[i][1] = s
time_list[i][0] = e
# 정렬 : 그냥 sort를 하게 되면 자동으로 0번째 기준으로 정렬하고 같다고 1번째 기준으로 정렬해줌
time_list.sort()
