11047. 동전 0

문제가 궁금하시다면 아래의 링크를 눌러주세요!
문제 본문

접근 과정

• 사실 K보다는 동전의 종류 N에 주목해야 한다!
• 다행히 각 동전들은 큰 동전이 작은 동전의 배수인 형태이다.
• 그 말은...?
  • 그리디하게 풀 수가 있다는 것이다!
  • 배수가 아닌 경우 그리디로는 해를 구할 수 없다...(왜 그럴까?)
    
    
• 가장 큰 동전부터 차례대로 내려온다. N의 값이 K보다 크다면, 건너뛴다.
• N의 값이 K보다 작다면, K를 N으로 나눈 몫을 동전의 개수에 더해주고, K에서 동전 * 몫만큼을 차감한다.
• K가 0이 될 때까지 이를 반복해준다.
• 이를 통해 O(N) (N은 동전 개수)의 복잡도로 필요한 최소한의 동전 개수를 구할 수 있을 것이다.
• 시간 제한은 1초! 위의 복잡도라면 통과할 것이다.
  
  

풀이

N, K = map(int, input().split())
money = [int(input()) for i in range(N)]
cnt = 0

for i in range(len(money) - 1, -1, -1):   # 큰 동전부터 가야하기 때문! 아예 [::-1]로 리스트를 뒤집어놓고 시작해도 될듯
    if K == 0:                            # K가 0이 된 경우(금액을 맞춘 경우) 탈출한다.
        break

    if money[i] > K: continue             # 동전이 K보다 큰 경우 건너뛴다.(나눌 수 없기 때문)

    cnt += K // money[i]                  # 몫만큼을 동전의 개수에 더해주고
    K -= money[i] * (K // money[i])       # 금액을 차감한다. 금액 K가 0이 된다는 것은 처음에 주어진 금액 K를 맞추었다는 것을 의미한다.

print(cnt)

읽어주셔서 감사합니다!