-
[백준] 11047: 동전 0 (그리디)development/알고리즘 2024. 3. 22. 18:09
안녕하세요.
이번 문제는 백준의 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원이 목표 금액일 때)를 신경 써야 합니다.
- 저도 사실 한번 틀리고 테스트 케이스를 추가해서 생각해보고 맞췄습니다.
알고리즘 캔버스
감사합니다.
'development > 알고리즘' 카테고리의 다른 글
[프로그래머스] 60057: 2020 KAKAO BLIND RECRUITMENT > 문자열 압축 (0) 2024.04.05 [프로그래머스] 120812: 최빈값 (1) 2024.03.29 [프로그래머스] JadenCase 문자열 만들기 (0) 2022.09.11 [프로그래머스] 가장 큰 수 (0) 2022.08.31 [프로그래머스] K번째 수 (0) 2022.08.30