[백준] 11047번

백준 11047번

그리디

그리디를 이용하는 문제였다.

내 풀이

1 5 10 50 100 500 1000 5000 10000 50000
를 리스트로 받아서 이를 내림차순으로 정리를 해야겠다고 생각했다.
그러면 순서가
[50000 10000 5000 1000 500 100 50 10 5 1]이 된다.
여기서 내가 한 실수는 입력에 아직 서툴어서 그런지 이를 문자열로 입력을 받아버려서 sort(reverse=True)로 해버리면 문자열처럼 정렬이 되어서 앞자리 숫자가 큰 순서로 이상하게 정렬된다.
그래서 꼭 숫자 리스트로 받아야한다는 것을 배웠다.
append를 통해서 리스트에 추가해주자.

graph= []
graph.append(int(input())

이렇게 숫자를 내림차순으로 정리를 했으면 4200원이라면 몫이 1과 같거나 큰 숫자로 바로 나누는게 젤 효율이 좋아서 4200 // 1000 은 몫이 4가 된다. 따라서 4를 cnt에 담아주고 4200 % 1000을 해주면 나머지가 200원이 된다. 200을 다시 몫이 1과 같거나 큰 숫자인 100으로 나눈다. 이렇게 for문을 돌려주고 cnt에 더해준다.

내 코드

N,K = map(int,input().split())
graph= []
for _ in range(N):
    graph.append(int(input()))
graph.sort(reverse=True)
cnt= 0
for i in range(N):
    if K // int(graph[i]) >=1:
        cnt += K //int(graph[i])
        K %= int(graph[i])
print(cnt)