189-A, *1300

Problem - 189A - Codeforces

문제

• 세 정수 $a,\ b,\ c(1 \leq a,\ b,\ c \leq 4000)$가 주어진다
• 길이가 $n(1 \leq n \leq 4000)$인 끈을 길이 $a,\ b,\ c$로만 자를 때 나오는 조각의 최대 개수는?

 

$O(n)$

$DP_{i}$를 길이가 $i$인 끈을 길이 $a,\ b,\ c$로만 자를 때 나오는 조각의 최대 개수라고 하자. 그러면
$$\mathrm{DP_{i}=max(DP_{i-a},\ DP_{i-b},\ DP_{i-c})+1},\ \mathrm{Not\ all\ of\ DP_{i-a},\ Dp_{i-b},\ Dp_{i-c}=0}$$

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
 
int n, a, b, c;
int dp[40001] {};
 
int Maxval(int a, int b, int c)
{
    int maxval = a;
    if(maxval < b) maxval = b;
    if(maxval < c) maxval = c;
    return maxval;
}
 
int Dp(int ind)
{
    if(ind >= 0) return dp[ind];
    else return 0;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> a >> b >> c;
    dp[a] = 1;
    dp[b] = 1;
    dp[c] = 1;
    for(int i = 1; i <= n; i++) {
        if(Dp(i-a) or Dp(i-b) or Dp(i-c)) dp[i] = Maxval(Dp(i-a), Dp(i-b), Dp(i-c)) + 1;
    }
 
    cout << dp[n] << endl;
 
    return 0;
}cs

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int n, a, b, c;
    cin >> n >> a >> b >> c;
    int cz;
    int maxval = 0;
    for(int x = 0; x <= 4000; x++){
        for(int y = 0; y <= 4000; y++){
            cz = n - a*x - b*y;
            if(cz >= 0 && cz%c == 0){
                maxval = max(maxval, x+y+cz/c);
            }
        }
    }
 
    cout << maxval << endl;
 
    return 0;
}cs