[C++] BOJ (백준) 2839 : 설탕 배달

문제

2839번: 설탕 배달 (acmicpc.net)

2839번: 설탕 배달

코드 1 (그리디)

#include <iostream>

using namespace std;

int getMinCount(int n) {
  for (int five = n / 5; five >= 0; five--) {
    int remainder = n - five * 5;
    if (remainder % 3 == 0) return five + remainder / 3;
  }
  return -1;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  cout << getMinCount(n);
}

 

설명

5킬로그램 봉지를 가능한 한 많이 선택한다.
남은 무게를 3킬로그램 봉지로 채우는 것이 불가능하다면 5킬로그램 봉지를 하나씩 덜어내면서 확인을 반복한다.

 

코드 2 (DP)

#include <iostream>

#define INF 987654321

using namespace std;

int dp[5001];

int getMinCount(int n) {
  if (n < 0) return INF;
  if (dp[n]) return dp[n];
  return dp[n] = min(getMinCount(n - 3) + 1, getMinCount(n - 5) + 1);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  dp[3] = 1;
  dp[5] = 1;

  int n;
  cin >> n;
  int res = getMinCount(n);
  if (res > INF) res = -1;
  cout << res;
  return 0;
}

설명

먼저 몇가지 경우를 직접 적어보면서 규칙을 찾아보자.

3 = 3
5 = 5
6 = 3+3
8 = 3+5
9 = 3+3+3 = 3+6
10 = 5+5
11 = 3+3+5 = 3+8
12 = 3+3+3+3 = 3+9
13 = 3+5+5 = 3+10
14 = 3+3+3+5 = 3+11
15 = 5+5+5 = 5+10

3과 5를 제외하면 모두 3+? 또는 5+? 의 형태로 바꿀 수 있다.
따라서 점화식, 즉 DP로도 풀이가 가능하다.