-
11047. [Python]동전 0Python_알고리즘/Silver IV 2023. 1. 30. 21:15
1. 문제
https://www.acmicpc.net/problem/11047
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
2. 접근 방법
- 시간 제한: 1초
- 메모리 제한: 256MB
- 탐욕 알고리즘(Greedy Algorithm)
3. 파이썬 코드
N,K = map(int,input().split()) # 돈 담을 리스트 생성 money = [] for _ in range(N): money.append(int(input())) cnt = 0 # K 라는 목표값이 0일때까지 반복 while K>0: # 리스트의 돈이 큰값부터 배열 반복 for i in range(len(money)-1,-1,-1): # 높은 값의 돈부터 반복하기 때문에 그값의 몫이 0이 아닌 경우 그 몫 저장 if K // money[i] > 0: cnt += (K // money[i]) # K 에는 나머지 값 저장 K %= money[i] print(cnt)
4. 문제를 풀고난 후 생각
- 동전 계산문제는 Greedy Algorithm에 자주 나오는 문제이다. 큰 동전부터 값을 넣어서 작은동전의 사용 갯수를 줄여나가는 방식으로 진행된다.
- 문제에서는 사용하는 동전의 가격이 세분화되어 간단하게 구현할 수 있던 문제였다.
- 높은 동전이 몇개 들어가는지 몫을 구하고 나머지를 다시 변수로 넣어주고 다음 동전으로 넘어가서 똑같은 행동을 반복하며 갯수를 체크한다.
5. 문제를 푸는데 도움이 되는 지식
- 탐욕 알고리즘(Greedy Algorithm)
'Python_알고리즘 > Silver IV' 카테고리의 다른 글
10610. [Python]30 (0) 2023.01.31 1789. [Python]수들의 합 (0) 2023.01.30 2217. [Python]로프 (0) 2023.01.29 11399. [Python]ATM (0) 2023.01.26 1459. [Python]걷기 (0) 2023.01.25