https://www.acmicpc.net/problem/14916
14916번: 거스름돈
첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.
www.acmicpc.net

난이도: solved.ac 실버 5
요즘 dp 문제를 푸는 중이라 이 문제를 dp방식으로 풀어보았다
근데 이 문제 리뷰를 보고 옛날에 풀었던 2839번과 똑같은 문제라는 걸 알게 되었다
https://blog.naver.com/jahysu7300/222511147813
[C언어] 백준 2839번 : 설탕 배달
이 문제는 솔직히 나한테 너무 어려웠다... 오늘 생각날 때마다 계속 고민을 해봐도 어떻게 해야 풀 수 있...
blog.naver.com
그래서 이전에 풀었던 방식(Greedy Algorithm)으로도 풀어보았다
먼저 dp풀이부터 소개하겠다
다이나믹프로그래밍(dp) 풀이
n열까지의 열을 가진 배열 arr을 동적할당하였다
2원과 5원으로 거슬러 줄 수 없으면 -1을 출력하므로
arr[0]부터 arr[n]까지의 배열을 -1로 초기화 시켜주고
2원과 5원은 각각 하나의 2원과 5원으로 거슬러 줄 수 있으므로
arr[2] = 1, arr[5] = 1으로 초기화 해주었다
n = 3 부터는 arr[n - 2] 또는 arr[n - 5]이 -1이 아닌 경우에서
arr[n - 2] + 1과 arr[n - 5] + 1 중 더 작은 걸 arr[n]이라고 해주었다
예를 들어, n = 13 일 때를 보자
arr[2] = 1
arr[3] = -1
arr[4] = arr[4 - 2] + 1 = 2
arr[5] = 1
arr[6] = arr[6 - 2] + 1 = 3
arr[7] = min(arr[7 - 2] + 1, arr[7 - 5] + 1) = min(2, 2) = 2
arr[8] = arr[8 - 2] = 4
arr[9] = min(arr[9 - 2] + 1, arr[9 - 5] + 1) = min(3, 3) = 3
arr[10] = min(arr[10 - 2] + 1, arr[10 - 5] + 1) = min(5, 2) = 2
arr[11] = min(arr[11 - 2] + 1, arr[11 - 5] + 1) = min(4, 4) = 4
arr[12] = min(arr[12 - 2] + 1, arr[12 - 5] + 1) = min(3, 3) = 3
arr[13] = min(arr[13 - 2] + 1, arr[13 - 5] + 1) = min(5, 5) = 5
으로
n = 13 일 때는 동전의 최소 개수가 5가 된다
이를 코드로 나타내면 아래와 같다
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #define min(A,B) A < B ? A : B int main() { int n, i, j; scanf("%d", &n); int* arr = (int*)calloc(n + 1, sizeof(int)); for (i = 0; i < n + 1; i++) arr[i] = -1; arr[2] = 1; arr[5] = 1; for (i = 3; i < n + 1; i++) { if (arr[i - 2] != -1) arr[i] = arr[i - 2] + 1; if (arr[i - 5] != -1 && i > 5) arr[i] = min(arr[i], arr[i - 5] + 1); } printf("%d", arr[n]); return 0; }
그리디 알고리즘(Greedy Algorithm) 풀이
5로 나누어 떨어질 때까지 n에서 2씩 빼는 방식이다
#include<stdio.h> int main() { int n, count = 0; scanf("%d", &n); if (n % 5 == 0) printf("%d", n / 5); else while (n > 0) { n -= 2; count++; if (n % 5 == 0) { printf("%d", count + n / 5); break; } } if (n < 0) printf("-1"); return 0; }