*(백준BAEKJOOB )* 14916 거스름돈

문제 출처

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

14916번: 거스름돈

 

문제풀이

개인적으로 동적 계획 알고리즘으로 풀려다 보니까

좀 어려웠다.

코드

#include<iostream>
#include <algorithm>
#include <vector>
using namespace std;

int dp[100001], coin[2] = { 2,5 }, n;

int w(int v) {
	if (v < 0)return 1e9;
	if (v == 0)return 0;
	if (dp[v] > 0)return dp[v];
	int inf = 1e9;
	for (int i = 0; i < 2; i++) {
		inf = min(inf, w(v - coin[i] ) + 1);
		dp[v] = inf;
	}
	return inf;
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n;
	if (n % 5 == 0)cout << n / 5; 

	else {
		int res = w(n);
		if (res == 1e9)cout << "-1";
		else cout << res;

	}
}

+

 

알고리즘 말고 일반 방식으로 풀기

이방법은 2원과 5만 있으니까 가능한 방식이다.

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int n, cnt = 0;
	cin >> n;
	while (n > 0) {
		if (n % 5 == 0) {
			cout << n / 5 + cnt;
			return 0;
		}
		cnt++;
		n -= 2;
	}
	cout << "-1";
	return 0;
}

 

 

 

설명

동적 계획 알고리즘 (dp) 의 개념만 알고 코드를 짜보는건 처음이였다.

2일 소요 했지만 관련 문제들을 많이 풀어 봐야겠다.