문제

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

• 그리디 문제

풀이

문제의 조건 중에서 A[i]는 A[i-1]의 배수라고 명시되어있기 때문에 그리디로 접근해서 풀 수 있다는 것을 알 수 있다. 배열 coins 에 input을 넣은 후 역순으로 loop를 돌면서 K값과 input값을 비교하며, 값이 작거나 같은 경우에 해당 값으로 K를 나누어주고 나머지를 K에 할당하였고, 동전의 갯수는 rst 변수에 담는 방식으로 풀이했다.

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

rst = 0
for money in coins[::-1]:
    if money <= K:
        rst += K // money
        K %= money

print(rst)

후기

문제에서 주어지는 조건을 잘보고 그리디로 접근할 수 있는지 파악을 확실하게 해야한다. 해당 문제에서는 직접적으로 그리디로 접근할 수 있다는 힌트를 주었지만 어려운 문제에서는 주어지지 않을 확률이 높다.