[BOJ] 11047번 동전0 / 사용언어 : 파이썬(python)

※ 문제링크

11047번: 동전 0

※ 관련개념

탐욕법(그리디) 알고리즘

해당 문제는 그리디 알고리즘을 활용하여 푸는 문제였다. 사실 그리디 알고리즘이 정확히 무엇인지 몰라도 문제를 풀 수 있었으나, 그리디 알고리즘의 개념을 확인하기 위해 구글링 통해 개념을 확인하여 봤다. 그 중에서 가장 잘 그리디 알고리즘 개념을 설명하고 있는 블로그가 있어서 링크를 걸어보았다. 구체적인 문제풀이 방법과 코드는 아래와 같다.

1. 입력받은 금액의 크기를 리스트에 저장해준다.

2. 끝에서부터 K를 나눌 수 있으면 K를 금액을 나눈 몫만큼 카운트에 추가 후, K는 금액으로 나눈 나머지로 반환한다.

3. K값이 0이 되면 반복문을 종료하고 cnt값을 출력한다.

 

N, K = map(int, input().split())
c_list = [int(input()) for _ in range(N)]
cnt = 0
i = N-1
while K > 0:
    if c_list[i] <= K:
        cnt += K // c_list[i]
        K = K % c_list[i]
    else: 
        i -= 1
print(cnt)

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.