백준 14916 거스름돈을 푸는 다양한 방법

www.acmicpc.net/problem/14916

14916번: 거스름돈

 

처음 풀이-dp

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

int dp[100001], coin[2] = { 2,5 }, n;
int f(int v) {
	if (v < 0) return 1e9;
	if (v == 0) return 0;
	if (dp[v] > 0) return dp[v];
	int res = 1e9;
	for (int i = 0; i < 2; i++) {
		res = min(res, f(v - coin[i]) + 1);
		dp[v] = res;
	}
	return res;
}

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

	cin >> n;
	if (n % 5 == 0) cout << n / 5; //5로 나눠지면 무조건 이득
	else {
		//다 해 봐야 함
		int res = f(n);
		if (res == 1e9) cout << "-1";
		else cout << res;

	}
}

dp로 풀었다

사실 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;
}

5로 나눠보고 안 나눠지면 2를 빼는 식

끝까지 안 되면 -1하고 끝

 

왜 이렇게 쉽게 풀 수 있는 문제도 어렵게 굳이 돌아서 풀려고 하지..

쓸 데 없는 곳에서 복잡하게 생각하는 안 좋은 습관이 들었다

 

위에 코드랑 같지만 좀 더 간결한 방법

#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 % 5 == 0 || n <= 0)) {
        n -= 2;
        cnt++;
    }
    if (n < 0) {
        cout << "-1";
        return 0;
    }
    cout << n / 5 + cnt;
}

동작은 같지만 이렇게도 줄일 수 있긴 하겠다

숏코딩 하는 게 아니라면 이렇게 굳이 안 할 것 같지만

 

생각을 하고 풀기

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

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

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

    cout << sum;
    return 0;
}

1, 3은 무조건 안 되니까 바로 패스

5, 2로 다 나눠지면 그냥 나누면 된다

이도저도 아니면 n / 5 + n % 5 / 2 + n % 5 % 2 * 2;

 

이게 어떻게 가능하냐면,

일단 5원이 2원보다 크니까 5원을 더 쓰는 게 이득이다

거스름돈을 5원으로 나누면 나머지는 0,1,2,3,4가 나올 수 있다

 

나머지가 4, 2인 경우 2로 나눠지기 때문에 최소 동전의 개수는 거스름돈/5 + 거스름돈%5/2 한 값이다

 

나머지가 3, 1인 경우 2로 나눠지지 않기 때문에 5원 동전을 하나 덜 사용해서 나머지를 8, 6으로 만들어서 2로 나눠야 한다

이런 경우 최소 동전의 개수는 (거스름돈/5-1) + (거스름돈%5+5)/2이다