[ baekjoon ] #2839 설탕 배달

백준 #2839 설탕 배달

# Greedy Algorithm

💡 Idea

• N 킬로그램을 정확히 만들기 위해서는 3kg, 5kg 중 더 무거운 5kg로 나눠봐야한다.
• 5kg으로 나눈 나머지가 5kg로 나누어떨어지지 않는다면 3kg를 빼고 cnt를 하나 증가시켜준다.

  Source Code

  #include <iostream>
  using namespace std;
  
  int main() {
  	int N, cnt = 0;
  	cin >> N;
  	while (N >= 0) {
  		if (N % 5 == 0) {
  			cnt += N / 5;
  			break;
  		}
  		N -= 3;
  		cnt++;
  		if (N <= 0) break;
  	}
  
  	if (N < 0) cout << "-1";
  	else cout << cnt;
  	return 0;
  }

# Dynamic Programming

• 하나의 큰 문제를 여러 개의 문제로 나누어 그 결과를 저장하여 큰 문제를 해결할 때 사용
• 저장해 둔 값을 이용(메모이제이션)

💡 Idea

1. 문제를 해결하기 위해 dp 벡터를 생성한 후 MAX 값으로 초기화
   vector<int> dp(N+1, MAX);
2. 3kg일 때와 5kg일 때를 저장
   dp[3]=dp[5]=1
3. 6부터 N까지 해당 값에서 3kg를 골랐을 때와 5kg를 골랐을 때의 값을 비교해 작은 값 저장해주기

Source Code

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

#define MAX 999999

int main() {
	int N;
	cin >> N;
	vector <int> dp(N + 1, MAX);
	dp[3] = dp[5] = 1;
	for (int i = 6; i <= N; i++) {
		dp[i] = min(dp[i - 3] + 1, dp[i - 5] + 1);
	}
	if (dp[N] >= MAX)cout << "-1";
	else cout << dp[N];

	return 0;
}