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

풀이

1. DP를 활용해서 해결했다.

2. 타겟 값이 9라고 할 때 3과 5를 사용해서 9를 만들기 위해서는 직전 값이 6 또는 5만 가능하다.

3. 이때 dp[5], dp[6]에 저장된 값은 5, 6을 만들기 위해 최소로 필요한 봉지 개수이다.

3. 따라서 점화식, dp[n] = min(dp[n-3], dp[n-5])+1 을 세울 수 있다.

4. 추가로 dp[x] = 0 인 부분은 3과 5로 만들 수 없는 값이므로 조건문으로 배제하면 된다. 나는 3번의 if문을 통해서 해결했다. dp[i-3]이 있다면 업데이트, dp[i-5]가 있다면 업데이트, dp[i-3], dp[i-5] 둘다 있으면 최소값에 대해 업데이트 한다.

 

리뷰 

dp를 선언할 때 벡터로 선언하냐, 배열로 선언하냐에 따라 메모리 초과가 떳다. 나머지 조건문은 동일.

벡터로 선언했을 때는 따로 sol함수를 만드니 해결됐고, 배열로 할 때는 바로 해결이 됐다.

이 부분에서 왜 벡터로 선언하면 메모리를 초과하는지 잘 모르겠다... 프로그래머스 외톨이알파벳 문제에서도 동일하게 메모리 초과 문제가 있었다.

#include <iostream>
#include <vector> 

using namespace std; 

int sol(int num) 
{
    vector<int> dp(num+1, 0);
    dp[3] = 1;
    dp[5] = 1;

    for (int i=6; i <= num; i++) {
        if (dp[i-3]) dp[i] = dp[i-3]+1;
        if (dp[i-5]) dp[i] = dp[i-5]+1;
        if (dp[i-3] && dp[i-5]) dp[i] = min(dp[i-3], dp[i-5])+1;
    }

    if (dp[num] == 0) return -1;
    else return dp[num];

}

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

    freopen("2839.txt", "r", stdin);

    int num;

    cin >> num;
    cout << sol(num) << endl;

    return 0;
}

#include <iostream>
#include <vector> 
#include <cstring>

using namespace std; 

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

    // freopen("2839.txt", "r", stdin);

    int num;

    cin >> num;
    int dp[num+1];
    memset(dp, 0, sizeof(dp));
 
    dp[3] = 1;
    dp[5] = 1;

    for (int i=6; i <= num; i++) {
        if (dp[i-3]) dp[i] = dp[i-3]+1;
        if (dp[i-5]) dp[i] = dp[i-5]+1;
        if (dp[i-3] && dp[i-5]) dp[i] = min(dp[i-3], dp[i-5])+1;
    }

    if (dp[num] == 0) cout << -1 << endl;
    else cout << dp[num] << endl;

    return 0;
}