11047 동전0 _python

https://www.acmicpc.net/problem/11047

11047번: 동전 0

고생하지말고 문제부터 잘 읽자...

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 접근

동전을 최소한 적은 개수로 K만큼의 가치를 만들자.

처음엔 재귀함수로 구현했다.

입력이 만약 이렇게 주어진다면?

3 10

3

7

9

이렇게 입력받는다면 순차적으로 접근할 시 9를 먼저 빼버리고 1이남는데 10원을 만들 수 없다!

그러면 브루트포스알고리즘이 아닌가! 

재귀함수로 모든 경우를 탐색해도 안되더라...

 

입력 조건

(1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

무조건 배수로 주어지는 것이다. 순차적으로 빼주면 되는 문제였다.

 

1. 현재 금액에서 i번째 코인의 몫을 정답에 더한다.

2. 현재 금액에서 코인의 나머지를 저장한다.

끗..

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

코드

import sys
input = sys.stdin.readline

"""


"""

N, K = map(int,input().split())
coins = [int(input()) for _ in range(N)]
curMoney = K
ans = 0

for i in range(N-1, -1, -1):
    if coins[i] <= curMoney:
        ans += curMoney // coins[i] 
        curMoney %= coins[i]

print(ans)