본문 바로가기

거스름돈 문제1

[Python] 백준 1398 동전 문제 문제 링크 : https://www.acmicpc.net/problem/1398 1398번: 동전 문제 김형택이 세운 나라의 화폐 체계는 단순하다. 이곳은 동전만 사용하고, 동전은 다음과 같이 다른 값을 가진다. 1, 10, 25, 100, 1000, 2500, 10000, 100000, ... 식으로 나타내면 0보다 크거나 같은 모든 K에 www.acmicpc.net 1. 접근 방법 기본적인 접근은 거스름돈 문제처럼, 해당 금액을 가장 큰 금액으로 채우는 것으로 시작했다. 그런데, 10과 25가 약수 / 배수 관계가 아니라서 일반적인 방법으로 해결하지 못한다. (30일 때, 10 + 10 + 10이 최소이지만, 큰 값 부터하면 25 + 1 + 1+ 1+ 1+ 1으로 최소가 아니게 됨) 그래서 전반적인 .. 2021. 10. 8.

티스토리툴바