149161 [백준] 14916번 거스름돈 JAVA (자바) 풀이 문제 14916번 (DP) : 거스름돈 = 2원, 5원 : 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램 : 예) 거스름돈이 15원이면 5원짜리 3개, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개 [입력] : 첫째 줄에 거스름돈 액수 n (1 ≤ n ≤ 100,000) [출력] : 거스름돈 동전의 최소 개수를 출력 (거슬러 줄 수 없으면 -1 출력)[설명] DP 알고리즘: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법 DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다 탑다운 (Top-Down) 보텀업 (Bottom-Up)작은 크기로 문제를 나.. 2024. 6. 11. 이전 1 다음