백준 11047번 Python

그리디 알고리즘

currency_total=list(map(int,input().split()))
price=[]
for i in range(currency_total[0]) :
    userinput=int(input())
    price.append(userinput)

current_value = currency_total[1]
position=currency_total[0]-1
result=0

while 1 :
    if (current_value-price[position]) < 0:
        position-=1
    
    else :
        temp=current_value//price[position]
        result+=temp
        current_value-=temp*price[position]
        if current_value == 0 :
            print(result)
            break
        position-=1

문제에 처음 접근 시에 생각한 것은 가장 큰 수를 차근차근 빼면 되겠다고 생각했다. 주어진 문제에서 A의 첫번째값이 1이고 다음 A의 값들이 배수로 다음 값을 전 값으로 나눌 수 있기 때문에 - 값이 나오는 것을 고려 할 필요는 없었다. 해당 문제를 풀면서 여러 차례 시간 초과로 실패를 하였다. 그 이유가 처음에 생각했던 내용인 큰 수부터 차근차근 빼는 방법으로 while문을 통과 할 때마다 뺄셈연산을 하도록 코딩을 하였다. 하지만 작은 수면 상관 없었지만, 1억이라는 큰 수를 계산 하게 되면, 시간 복잡도가 기하 급수적으로 증가 할 것이라는 생각을 하지 못하였다. 그래서 현재 값을 만들어야 하는 값에서 현재 계산 할 동전의 값을 나누어 몫을 결과값에 더하는 방식으로 답을 도출하였다.