문제

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

전략과 후기

그리디 알고리즘은 매 순간마다 가장 유리한 경우를 선택하는 방식으로 풀어야 한다. -> 동적계획법과 비교됨
-> M보다 가치가 작은 동전 중 가장 큰 가치값을 가진 동전으로 빼는 전략

1. 처음 풀때 너무 단순히 생각하고 풀었다 -> 그냥 뺼샘 여러번 -> 몫이랑 나머지 생각못함 (시간초과뜨고나서 알음) -> 뺄셈여러번은 나눗셈으로 한번에 할 수있다라는 생각을해야지!! 덧셈과 곱셈도 마찬가지일테고~
2. M이 모든 동전의 가치보다 클경우를 첨에 고려안했었음 -> 런타임에러 -> 질문검색에서 찾아서 꺠달았지 안그랬으면 몰랐을듯

쉬운문제도 두번보자.

예제의 입력값 외의 경우 반드시 고려

꼭 생각!!!! 예제 입력값은 일부러 좁은 입력값 범위만 제공해줄 가능성이큼! 보통 극한의 경우 완전 입력값이 적을떄, 많을떄, 여사건의 경우를 생각하는게 좋다.

코드

import sys

inputNM= sys.stdin.readline().split(" ")
N=int(inputNM[0])
M=int(inputNM[1])
inputLs= []
for i in range(N):
    inputNum = int(sys.stdin.readline())    
    inputLs.append(inputNum)

for i in range(N):
    if inputLs[i] > M:
        index = i-1
        break
    elif i == N-1:
        index = N-1

count =0
while M >0 :
    
    if inputLs[index] > M:
        while inputLs[index] >M:
            index-=1

    divider = M// inputLs[index]
    M-= divider * inputLs[index]
    count+=divider

print(count)