[SWEA] 8275 햄스터

 

입력받는 숫자들을 보면 엄청 작다

완탐으로 정말 다 찾아보면 된다

 

답이 여러개라면 숫자가 많은것 중에 사전순으로 앞에오는 것을 출력해야한다

따라서 각 자리마자 0~x까지 넣어보면서 햄스터 수를 만족하고

현재 답보다 합이 크다면 계속 바꿔주면 된다!

 

소스코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int t,n,x,m;
pair<pair<int,int>,int> arr[11];
int maxcnt;
int ans[11];
void solve(int pos,int sum,vector<int>& vt){
    if(pos==n){
        if(sum>maxcnt){
            for(int i=0;i<m;i++){
                int l = arr[i].first.first;
                int r = arr[i].first.second;
                int cnt = arr[i].second;
 
                int tempcnt=0;
                for(int j=l;j<=r;j++) tempcnt+=vt[j];
                if(tempcnt!=cnt) return;
            }
            for(int i=0;i<n;i++) ans[i]=vt[i];
            maxcnt=sum;
        }
        return;
    }
    for(int i=0;i<=x;i++){
        vt[pos]=i;
        solve(pos+1,sum+i,vt);
    }
}
int main(){
    scanf(" %d",&t);
    for(int tc=1;tc<=t;tc++){
        maxcnt=-1;
        scanf("%d %d %d",&n,&x,&m);
        for(int i=0;i<m;i++){
            int l,r,q; scanf(" %d %d %d",&l,&r,&q);
            arr[i]= {{l-1,r-1},q};
        }
        vector<int>vt(n);
        solve(0,0,vt);
        
        printf("#%d ",tc); 
        if(maxcnt==-1) printf("-1");
        else for(int i=0;i<n;i++) printf("%d ",ans[i]);
        puts("");
    }
}