[문제풀이] 헬스홀스틴스.

USACO Training Gateway에서 OI를 되찾은 후 첫 번째 물문제를 일정 시간 조정했는데 주로 경계를 잘 고려하지 않았기 때문에 이번에 코드를 쓰는 습관이 괜찮다. 간단한 DFS는 경계 설정에서 물러나는 것이 관건이다.코드가 못생겼어요.

#include
#include
#include
#include
#include
#include
using namespace std;

int v,g,t;
int m=100;
int w[30],s[20][30],f[20],r[20];
void work(int d)
{
 int i,c=0;
 if(d>g+1) return;
 int b=1;
 for(i=1;i<=v;i++)
   if(w[i]>0)
    {
    b=0;
    break;
}

 if(b==1) {
  if(m>t)
  {
   m=t;
   for(i=1;i<=g;i++)
    if(f[i])r[++c]=i;
  }
  return;   
 }

 f[d]=1;
 t++;
 for(i=1;i<=v;i++)
  w[i]-=s[d][i];
 work(d+1);

 f[d]=0;
 t--;
 for(i=1;i<=v;i++)
  w[i]+=s[d][i];
  work(d+1); 

}
int main()
{
 cin>>v;
 for(int i=1;i<=v;i++)
  cin>>w[i];
 cin>>g;
 for(int i=1;i<=g;i++)
  for(int j=1;j<=v;j++)
   cin>>s[i][j];
 work(1);
 cout<" ";
 for(int i=1;i<=m;i++)
  cout<" ";      
}