[백준 알고리즘]11047 번 (Python)

 

문제 출처

www.acmicpc.net/problem/11047

11047번: 동전 0

1. 동전의 가치를 오름차순으로 입력받는다.

2. 주어진 합을 만들기 위해 필요한 최소한의 동전의 개수를 만드려면 가치가 큰 동전부터 더하면 된다.

3. 오름 차순으로 이루어진 배열을 역순으로 정렬해준다.

4. 맨 처음 더해야 하는 수가 주어진 합보다 크지 않는 것만 더해준다.

5. 그 후 주어진 합을 만들기 위해 가장큰 값들만 더해준다.

6. 사용된 동전의 갯수를 출력한다.

 

N,K = map(int,input().split())

valueList =[]
for i in range(N) :
    valueList.append(int(input()))

valueList.reverse()
result =0
count =0
index = 0
while result!=K :
    if valueList[index]>K :
        index+=1
        continue
    else :
        while (K-result)>=valueList[index] :
            result += valueList[index]
            count +=1
        index+=1
print(count)