読者です 読者をやめる 読者になる 読者になる

AOJ 1045 Split Up!

C/C++ Algorithms AOJ DFS

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1045

日本語。

解法

適当にDFSすればできる。

コード

int n;
int a[128];

int dfs(int p, int g, int c){
  if(n == c) return abs(p-g);
  return min(dfs(p+a[c], g, c+1), dfs(p, g+a[c], c+1));
}

int main(){
  while(scanf("%d", &n) && n){
    rep(i, n) scanf("%d", a+i);
    printf("%d\n", dfs(0, 0, 0));
  }
  return 0;
}

再帰の部分が簡潔にかけたと思う。