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
이전 풀이
https://dmaolon00.tistory.com/50
[백준_python] 동전 0 || 11047 (그리디 알고리즘)
11047번: 동전 0 (acmicpc.net) 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000,..
dmaolon00.tistory.com
n, k = map(int, input().split(' '))
coin = []
for i in range(n):
coin.append(int(input()))
cnt = 0
for i in range(n-1, -1, -1):
if(coin[i] <= k):
a = k // coin[i]
cnt += a
k = k - a * coin[i]
print(cnt)오름차순으로 동전들이 주어지기 때문에 역순으로 가장 큰 동전부터 계산을 해주었다.
이전 풀이에서는 남은 동전을 빼주며 구해주기 보다는 나머지를 계산하여 구해주었었다.
저번이랑 거의 같게 풀이를 했는데 틀렸습니다를 많이 본 이유,,,,,, = 을 안붙여줘서 알게 되었다.
반례로 1 1, 1을 넣어보고서야 깨달았다..ㅎㅎㅎ
시간 차이는 이전 풀이에서는 아무래도 for문 내에 k가 0이 되면 break를 해주어서 그런 것 같다.
딱히 없어도 상관은 없다.!
반응형