백준 2839번의 두가지 해결

Brute-Force

#include <iostream>
using namespace std;

int main() {
    int N;
    cin >> N;
    int x = N / 5;

    int answer = -1;

    while (x > 0) {

        if ((N - (x * 5)) % 3 == 0) {
            answer = x + ((N - (x * 5)) / 3);
            break;
        } else {
            x -= 1;
        }
    }
    cout << answer;
}

Dynamic Planning

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

int minBagsOfSugar(int N) {
    // 불가능한 무게에 대한 값으로 충분히 큰 수 설정
    const int INF = 5001; // N의 최대값보다 큰 수
    vector<int> dp(N + 1, INF);

    // 0kg의 경우 봉지 수는 0
    dp[0] = 0;

    // 각 무게에 대해 최소 봉지 수 계산
    for (int i = 3; i <= N; i++) {
        if (i - 3 >= 0) {
            dp[i] = min(dp[i], dp[i - 3] + 1);
        }
        if (i - 5 >= 0) {
            dp[i] = min(dp[i], dp[i - 5] + 1);
        }
    }

    // 결과 반환
    return dp[N] == INF ? -1 : dp[N];
}

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

    int result = minBagsOfSugar(N);
    cout << result;
    
    return 0;
}