[백준] 11047: 동전 0 (그리디)

안녕하세요.

이번 문제는 백준의 11047번 입니다.

그리디 알고리즘을 사용해 푸는 문제입니다. 

 

저는 요즘 푸는 문제들은 `알고리즘 디자인 캔버스(이하 캔버스)`를 제게 더욱 잘 맞게 수정해서, 템플릿화 시켜서 사용하고 있습니다. 

그래서 해당 문제도 캔버스에 적어가며 풀었습니다. 문제 정리에 도움이 되는 것 같습니다. 

 

참고로 그리디 알고리즘이란 매 상황에서의 가장 좋은 선택지를 고르는 알고리즘입니다. 

그래서 특정 조건을 충족하지 않으면 일반적으로 최적의 해가 되기는 어렵습니다. 최적 값의 '근사값'이 목표입니다.

 

다음이 문제입니다. 실버 4 단계네요.

 

문제

 

코드

n, k = map(int, input().split())
n_l = list(map(int, [input() for i in range(n)]))

c = 0

for v in n_l[::-1]:
    if v <= k:
        c = c + k // v
        k = k - (k // v) * v

        if k <= 0:
            break
			
print(c)

 

- 놓치기 쉬운 부분으로, 동전 종류와 값이 완전히 맞아 떨어질 때 (예를 들어 5000원이 목표 금액일 때)를 신경 써야 합니다.

- 저도 사실 한번 틀리고 테스트 케이스를 추가해서 생각해보고 맞췄습니다. 

 

알고리즘 캔버스

 

 

감사합니다.