[Code Tree] 효율적으로 분배하기

정수 n이 주어졌을 때, 5의 용량을 가진 상자와 3의 용량을 가진 상자에 나누어 담으려 합니다.

가장 적은 상자를 써서 n을 모두 분배한다고 할 때의 상자의 개수를 출력하는 프로그램을 작성해보세요.

 

입력 형식

첫 번째 줄에 n이 주어집니다.

• 3 ≤ n ≤ 5000

출력 형식

가장 적은 상자를 사용할 때의 상자의 개수를 출력합니다.

만약 n을 정확하게 모두 나눌 수 없다면 -1을 출력합니다.

 

#include <iostream>

using namespace std;

int dp[5010];

void init(){

    for(int i = 0; i < 5010; i++) dp[i] = -1;

}

int main() {

    init();

    int n;

    cin >> n;

    dp[3] = 1;

    dp[5] = 1;

    for(int i = 3; i <= n; i++){

        if(dp[i] != -1){

            if(dp[i + 3] == -1 || dp[i + 3] > dp[i] + 1) dp[i + 3] = dp[i] + 1;

            if(dp[i + 5] == -1 || dp[i + 5] > dp[i] + 1) dp[i + 5] = dp[i] + 1;

        }

    }

    cout << dp[n];

    return 0;

}

 

 

*박스, 동전 등등 일정한 단위를 가진 object로 어떤 정수를 가장 적은 숫자의 개수로 나누는 경우 dp이다.

*dp배열은 1차로 충분했고, n이 5000까지 이므로 여유롭게 5010으로 길이를 둬 out of index 에러를 방지했다.