오늘 푼 문제

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

설탕배달

• 풀이 방식
  5를 채우다가 안되면 3을 채우는 방식을 쓰면 되지 않을까라는 생각으로 풀었다. 예를 들어 4kg 설탕이라면 5로 나누어 떨어지지 않으므로 3을 계속 빼는데 3을 계속 빼는 동안 while문을 탈출하기때문에 실제로 4kg 설탕을 5kg, 3kg 봉투에 못넣는 상황처럼 된다.

나의 풀이

#include <iostream>

using namespace std;

int main() {

	
	int N;
	cin >> N;
	int count = 0;

	while (N >= 0) {
		if (N % 5 == 0) {
			count += (N / 5);
			cout << count << endl;
			return 0;
		}
		N -= 3;
		count++;
	}

	cout << -1 << endl;

	return 0;
}

• 다른풀이

#include <iostream>
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;
}

dp방식으로도 풀 수 있다는 것을 알았다.
최소를 구하는 방식으로 접근한다면 dp방식도 생각해볼만한 방식이라고 생각했다.