[백준] 동전0 풀이

핵심 아이디어는 '반대로 생각하기' 입니다. 즉, 여러 개의 동전들의 합을 조합하여 K원을 맞추지 말고,
K원에서 가치가 큰 동전들로 나누기/나머지 연산 등을 통하여 0원을 만들어 나가는 게 핵심인 것 같습니다.

입력받은 동전의 가치들을 내림차순 정렬을 통하여 가치가 큰 값이 리스트의 앞 요소에 오게끔 합니다.
반복문을 통하여 리스트의 각 요소들을 돌며, 동전의 갯수를 저장하는 변수에
현재 가지고 있는 돈 / 리스트의 현재 요소의 가치를 더하게끔 하였습니다.
또한, 다음 줄의 코드에서 현재 가지고 있는 돈을 현재 리스트의 요소와 나머지 연산을 통한 값으로 업데이트 하였습니다.

만약, 현재 가지고 있는 돈보다 리스트 요소가 더 크게 되어도, 결과에 아무런 영향을 끼치지 않습니다.
자신보다 더 큰 값으로 나누면 0이고, 자신보다 더 큰 값으로 나머지 연산을 하면 자기 자신이기 때문입니다.

소요 시간을 줄이기 위하여 현재 가지고 있는 돈이 0이 되면 break를 통하여 반복문을 빠져 나오게 하였고,
출력문으로 답을 출력하는 식으로 문제를 풀었습니다.

아래는 코드입니다.

N, K = map(int, input().split())
worth = []
cnt = 0  # 동전의 갯수를 저장할 변수

for i in range(N):
    worth.append(int(input()))

worth.sort(reverse=True)  # 큰 가치의 단위부터 나오도록 내림차순으로 정렬합니다.

for i in worth:
    cnt += K // i  # 바꿀 수 있으면 동전으로 해당 동전으로 최대한 바꾸는 코드입니다. 해당 동전의 가치가 가지고 있는 돈보다 크면 0으로 계산됩니다.
    K %= i  # 동전으로 바꾸고, 남은 돈을 다시 K에 저장하는 코드입니다. 해당 동전의 가치가 K보다 크면 현재 K값이 유지됩니다.