#10 [python] 11047번 동전 0

❗ 동전 갯수의 최솟값 구하기

[입력]

첫 줄에 N,K가 주어지고 둘째줄부터 N개의 줄에 동전 가격이 오름차순으로 주어짐

N, K # 동전수, 목표금액

 

[출력]

K원을 만드는데 필요한 동전 갯수의 최솟값 출력

 

✔️ 문제 분석

• 그리디 알고리즘 사용 문제
• 동전을 최소로 사용하려면 가격이 큰 동전부터 사용

1. 가격이 큰 동전부터 K보다 가격이 작거나 같은 동전 탐색
2. 값을 찾으면 값으로 K를 나눠 몫은 동전 갯수에 더하고 나머지는 K값으로 더하기
3. 0이 될 때까지 반복

💫 코드

N(동전 갯수) K(목표 금액)
A(동전 데이터 리스트)

for N만큼 반복:
	A 리스트 저장
# 가치가 큰 동전부터 선택해야 최소 갯수 구성 가능

for N: # n-1 ~0(역순)으로 반복
	if 현재 K보다 동전 가치가 작으면:
    동전 수 += 목표금액 / 현재 동전 가치
    목표 금액 = 목표 금액 % 현재 동전 가치
    
누적된 동전 수 출력

 

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:
        count += int(K/A[i])
        K = K%A[i]

print(count)

 

🔴

for i in range(10 , 1 , -1) # 10에서 1까지 역순으로 숫자 생성

 

 

 

 

 

참고 : https://velog.io/@jiyoon9-velog/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-14%EC%9D%BC%EC%B0%A8-%EB%8F%99%EC%A0%84-%EA%B0%9C%EC%88%98%EC%9D%98-%EC%B5%9C%EC%86%9F%EA%B0%92-%EA%B5%AC%ED%95%98%EA%B8%B0-%EC%B9%B4%EB%93%9C-%EC%A0%95%EB%A0%AC%ED%95%98%EA%B8%B0-%EC%88%98%EB%A5%BC-%EB%AC%B6%EC%96%B4%EC%84%9C-%EC%B5%9C%EB%8C%93%EA%B0%92-%EB%A7%8C%EB%93%A4%EA%B8%B0-%EB%B0%B1%EC%A4%8011047%EB%B2%88-%EB%B0%B1%EC%A4%801715%EB%B2%88-%EB%B0%B1%EC%A4%801744%EB%B2%88