백준 11047 파이썬 전형적인 그리디 알고리즘

백준 11047 파이썬 전형적인 그리디 알고리즘

2024. 5. 22. 06:55ㆍ코딩/백준

백준 11047 - 동전 0

문제

11047번: 동전 0

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

www.acmicpc.net

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

A = [0] * N

for i in range(N):

A[i] = int(input())

count = 0

for i in range(N - 1, -1, -1):

if A[i] <= K: # 현재 동전의 가치가 K보다 작거나 같으면 구성에 추가

count += int(K / A[i])

K = K % A[i] # K를 현재 동전을 사용하고 남은 금액으로 갱신

print(count)

# 문제 분석

# 전형적인 그리디 알고리즘

# 뒤의 동전 Ai가 앞에 나오는 동전 Ai-1의 배수가 된다는 조건

# 즉 가격이 큰 동전 먼저 사용하면 되는거임

그리디 알고리즘 정리 블로그

그리디 알고리즘과 우선순위 큐

그리디 그리디 알고리즘은 현재 상태에서 볼 수 있는 선택지 중에 최선의 선택을 하는 알고리즘이다. 그리디 알고리즘은 동적 계획법보다 구현하기 쉽고 시간 복잡도가 우수하다. 하지만 항상

mkisos.tistory.com