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

https://www.acmicpc.net/problem/2839

 

제출 코드

#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int count = 0;
    int n, left = 0;
    cin >> n;

    while (1)
    {
        if (n % 5 == 0) break;
        n -= 3;
        count++;
        if (n < 0)
        {
            cout << -1;
            return 0;
        }
    }
    cout << (n / 5) + count;
}

그리디나 DP에 대해 잘 모르고 작성한 코드라 밑에 각 접근법 별로 정리해두겠다

 

1. 그리디 알고리즘

그리디 알고리즘이란 매 단계마다 최적으로 보이는 선택을 반복해 최종적으로 최적에 가까운 해답을 찾는 과정이라고 한다

 

위 문제에서는 5kg짜리 봉지만 사용해서 운반이 가능하면 가장 최적이다

1. 우선 5kg짜리 봉지만 사용해서 운반이 가능한지를 체크(n % 5 == 0)

2. 운반이 불가하다면 3kg짜리 봉지를 하나 추가하면(n에서 3을 빼 준다) 나머지는 5kg로 운반이 가능한지 체크

3. 2번을 반복해서 체크하다, 조건을 만족하지 못했는데 남은 설탕의 양이 0보다 작아진다면 -1 출력

 

2. DP(동적 프로그래밍)

주어진 문제를 나눠서 하위 문제로 해결하여 이를 이용해 큰 문제를 해결하는 방법이라고 한다

다이나믹 프로그래밍에는 Top-Down 방식과 Bottom-up 방식이 존재한다

1) Top-Down: n번째부터 시작해서 0까지 내려간 다음, 결과값을 재활용하는 방식

2) Bottom-Up: 0부터 시작해서 n까지 가면서 값을 재활용하는 방식

 

1. 크기 5001짜리 배열(문제에서 n의 최댓값이 5000이므로)을 생성

2. n이 3일 때와 5일 때 각각 1봉지씩만 운반하면 되므로 값을 넣어두기(dp[3] = dp[5] = 1)

3. for loop를 돌면서 i - 3이나 i - 5의 값이 0이 아니라면(존재한다면) 해당 값에 봉지 하나를 더한 값을 dp[i]에 저장해 준다

* 이때 i - 3값이 존재해서 dp[i] = dp[i - 3] + 1을 저장해두었더라도, i - 5의 값도 존재한다면(이 경우가 더 봉지를 최소 갯수 운반하면 되므로) dp[i] = dp[i - 5] + 1값으로 재지정해줄 필요가 있다

#include <iostream>
using namespace std;

int dp[5001];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    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])
        cout << dp[n];
    else
        cout << -1;
}