백준 7671 - Baking Cakes

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

dp문제이고 냅색느낌이 많이난다.

int dp[시간1][시간2] 선언해준다.

먼저 오븐을 2개만 사용했을 때 가능한 시간의 조합수를
2중 for문을 돌면서 체크해준다.
(nC2 대신에 idx 를 sum(최대치)부터 시작해서 특정 v[i]가 중복되게 추가되는 것을 막았다.)

다음은 오븐을 한개 추가해서 답을 구하면 되는데
dp를 선언했다면 간단하다

dp[i][t] = true 라면
가능한 상황이므로
ans 의 후보는
sum-i-t,i,t 중 큰 것이 될 것이다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
bool dp[1201][1201];vector<int> v;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int N;
    while(1){
        cin>>N;
        if(N==0) break;
        v.clear();
        memset(dp,false,sizeof(dp));
        int sum = 0;
        for(int i=0;i<N;i++){
            int a;cin>>a;v.push_back(a);
            sum+=a;
        }
        dp[0][0]=1;
        for(int i=0;i<v.size();i++){
            for(int t=sum;t>=0;t--){
                for(int j=sum-t;j>=0;j--){
                    if(dp[t][j]){
                        dp[t+v[i]][j]=true;
                        dp[t][j+v[i]]=true;
                    }
                }
            }
        }
        int ans = sum;
        for(int i=0;i<=sum;i++){
            for(int t=0;t<=sum;t++){
                if(dp[i][t]){
                    int temp = max({sum-i-t,i,t});
                    ans = min(temp,ans);
                }
            }
        }
        cout<<ans<<"\n";
    }
}