백준 링크 : https://www.acmicpc.net/problem/2839

문제 개요

입력으로 N이 주어진다. 이 때 3과 5를 최소한으로 몇 번 써야 N을 구할 수 있는지 알아내는 문제이다.

출력으로는 사용된 3의 개수와 5의 개수를 각각 출력한다.

만약 구할 수 없으면 -1을 출력한다.

아이디어

1. DP를 통해 해결한다.
   • 결과값을 미리 배열에 캐싱하고, DP[N]의 값을 출력한다.
   • 이 때, 1 = -1, 2 = -1, 3 = 1, 4 = -1, 5 = 1로 초기화를 한다. 왜냐하면, 1, 2, 4는 무조건 값을 출력할 수 없으며, 3과 5는 무조건 1이기 때문이다.
   • DP[i]를 구하는 과정은 DP[i - 3]과 DP[i-5]중 작은 값을 선택하고 그 값에 +1을 한다.
2. 그리디 알고리즘을 통해 해결한다.
   • 5를 사용하는 것이 유리하므로 5를 최대한으로 사용하고 나머지를 3으로 사용한다는 논리로 해결한다.

주의사항

• N이 5000까지이며, 1초 시간 제한에 유의해야 한다.
  • 만약 재귀적으로 풀게 될 경우 시간 초과가 날 수 있다.

DP코드

// 아래의 코드는 dev c++환경에서 동작됩니다.
// visual studio에서는 bit/stdc++.h가 기본적으로 없기 때문에
// 정삭적인 작동이 되지 않을 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
int dp[5001];

int main() {
	int n;
	cin >> n;

	dp[3] = dp[5] = 1;	
	
	for (int i = 6; i <= n; i++) {
		if (dp[i - 3]) dp[i] = dp[i - 3] + 1;
		if (dp[i - 5]) dp[i] = dp[i] ? min(dp[i] , dp[i - 5] + 1) : dp[i - 5] + 1;
	}
	cout << (dp[n] == 0 ? -1 : dp[n]) << endl;
	return 0;
}

그리디 알고리즘 코드

// 아래의 코드는 dev c++환경에서 동작됩니다.
// visual studio에서는 bit/stdc++.h가 기본적으로 없기 때문에
// 정삭적인 작동이 되지 않을 수 있습니다.
#include <bits/stdc++.h>

using namespace std;

int n, ret;
int main() {
	cin >> n;
	
	while (n>=0) {
		if (n % 5 == 0) {	
			ret += (n / 5);	
			cout << ret << endl;
			return 0;
		}
		n -= 3;	
		ret++;	
	}
	cout << -1 << endl;
}

후기