[백준] 14916번: 거스름돈 - C언어 (dp, greedy 풀이 두 가지)

https://www.acmicpc.net/problem/14916

14916번: 거스름돈

난이도: solved.ac 실버 5

 

 

요즘 dp 문제를 푸는 중이라 이 문제를 dp방식으로 풀어보았다

근데 이 문제 리뷰를 보고 옛날에 풀었던 2839번과 똑같은 문제라는 걸 알게 되었다

https://blog.naver.com/jahysu7300/222511147813

[C언어] 백준 2839번 : 설탕 배달

 

그래서 이전에 풀었던 방식(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;
}