[BOJ][DP][브1][2839] 설탕 배달

문제 링크

설탕 배달/브1

첫 번째 풀이 : 완전탐색

Warning Notice: 두 번째 풀이가 더 나은 풀이입니다. 두 번째 풀이 이후 첫 번째 풀이의 문제점을 제시합니다.

알고리즘

1. 5킬로그램 봉지를 최대 N개 가져갈 수 있다고 할 때, 5킬로그램 봉지를 0~N개 가져가는 경우에 대해 2.를 진행한다.
2. 남은 설탕이 3킬로그램 봉지로 나누어 떨어지는지 확인한다.
3. 1.과 2.로 얻은 정답이 최소인지 매번 판단해서 저장한다.

정답 코드

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

int main(void) {
  int n, n_copy;
  int answer = 987654321;
  int ans_three, ans_five;
  cin >> n;
  
  for (int ans_five = 0; ans_five <= n / 5; ans_five++) {
    int rest = n - ans_five * 5;
    if (rest % 3 == 0) {
      answer = min(answer, ans_five + rest / 3);
    }
  }
  if (answer != 987654321) {
    cout << answer;
  }
  else {
    cout << -1;
  }
  return 0;
}

두 번째 풀이 : 완전탐색

알고리즘

1. 5킬로그램 봉지로 나누어 떨어지는지 확인한다.
2. 나누어 떨어지지 않으면 3킬로그램 봉지를 하나만 채워본다.
3. 다시 5킬로그램 봉지로 나누어 떨어지는지 확인한다.
4. 5킬로그램으로 나누어 떨어지지 않으면 계속 3킬로그램이 감소할 것이고, 마지막에는 0, -1, -2킬로그램이 남게 된다. 0이 남은 경우 3킬로그램으로 나누어 떨어진 경우, 아니라면 나누어 담지 못하는 경우이다.

정답 코드

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

int main(void) {
  int n;
  int ans_three = 0;
  cin >> n;

  while (n > 0 && n%5 != 0) {
    n -= 3;
    ans_three++;
  }
  if (n < 0) {
    cout << -1;
  }
  else {
    cout << n / 5 + ans_three;
  }
  return 0;
}

세 번째 풀이 : DP

알고리즘

마지막에 더해진 봉지는 5g 또는 3g입니다.

dp[i][0] = 마지막에 더해진 봉지가 5g인 경우 dp[i][1] = 마지막에 더해진 봉지가 3g인 경우

i가 3~7일 때는 직접 계산해서 저장해두고, 나누어 떨어지는 경우 방문처리를 합니다. 방문처리는 ig을 나누어서 담을 수 있다는 뜻입니다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

const int MAX = 5010;
const int MOD = 10007;
int arr[MAX][MAX];
ll dp[MAX][2];
bool visited[MAX];

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

int n, m;

void show(void);
void bfs(int x, int y);

int main()
{
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    dp[3][1] = 1; visited[3] = true;
    dp[5][0] = 1; visited[5] = true;
    dp[6][1] = 2; visited[6] = true;
    for (int i = 8; i <= n; i++) {
        if (visited[i - 3]) {
            dp[i][0] = dp[i - 3][0];
            dp[i][1] = dp[i - 3][1] + 1;
            visited[i] = true;
        }
        if ((dp[i][0] + dp[i][1]) < (dp[i - 5][0] + 1 + dp[i - 3][1])) {
            dp[i][0] = dp[i - 5][0] + 1;
            dp[i][1] = dp[i - 5][1];
            visited[i] = true;
        }
    }
    if (visited[n])
        cout << dp[n][0] + dp[n][1];
    else cout << -1;

    return 0;
}

결론

무게가 작은 봉지로 나누어 떨어지는지 확인하는 방법을 사용하면(첫 번째), 두 번째 풀이와 비슷한 풀이같지만 코드가 불필요하게 복잡해지는 문제점이 있을 수 있습니다.

for (int ans_five = 5; ans_five >=0 ; ans_five--) {
  if( (n - ans_five * 5) % 3 == 0){
    //pass
  }
}

Success Notice: 첫 번째 풀이의 문제점은 더 작은 킬로그람으로 나누어 떨어지는지 확인하는데에 있습니다. 무게가 큰 봉지로 나누어 떨어지는지 확인하는것이 더 좋은 방법입니다.