[백준] 2839 설탕 배달 c++

 

문제 링크 https://www.acmicpc.net/problem/2839

KEY

• 3과 5중에 5로 나누어 떨어지게 하는 것이 최소가 된다.

그리디 풀이

• 그리디 풀이의 경우 가령 18이 주어졌을 때, 5로 먼저 나누어 떨어지는지 보고, 아니라면 3씩 빼준다.(+1)
• 15가 되었을 때 5로 나누어 떨어지므로, 나눈 몫만큼 더해주면 (+3) 총 4번으로 배달 할 수 있다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
int N;
int answer;
int main() {
    cin >> N;
    while (N >= 0) {
        if (N % 5 == 0) { //5로 나누어떨어지면 몫만큼 answer에 더해주고 출력
            answer += N / 5;
            cout << answer << endl;
            return 0;
        }
        N -= 3;
        answer++;
    }
    cout << -1 << endl; 
}

 

동적계획법 풀이

• 동적계획법 풀이의 경우 1~N까지의 dp배열을 0으로 초기화 하여 3과 5로 나누어 떨어지는 수에 대해 +1을 해가는 식으로 풀 수 있다.
• 여기서 중요한 것은 3으로 나누어 떨어지는 dp값을 먼저 구한 다음, 5로 나누어 떨어지는 수의 dp값을 구해야 한다.
• (그래야 5로 나누어 떨어지는 수를 만날 때 최솟값으로 초기화할 수 있기 때문)

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
int N;
int dp[5001];
int main() {
    cin >> N;
    dp[3] = 1;
    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 - 5] + 1;
        }
    }
    if (dp[N]) //값이 0이 아니라면 dp[N]출력
        cout << dp[N];
    else
        cout << -1;
}