http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0030
正直全然わからなかったので調べてみると、どうやら深さ優先探索(Depth First Search)なることをするようです。ここでiは足す数、sは現在の合計(Sumが最終目標の合計)、nがあと何回足すかを表しています。
1 2 | dfs(i+1,s+i,n-1); //1 dfs(i+1,s,n); //2 |
この分岐にそれぞれ①②と番号をふったとすると、
①は足し算で②は場合分けの方向に分かれています。
画像はその時のメモです。(分かりづらい上にきたない…)
s == Sum かつ n == 0となれば、ひとつの組み合わせが見つかったので答えにカウントされます。
参考サイト(http://d.hatena.ne.jp/print7/20111004/1317697039)
以下、提出したソースコードです。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | #include <stdio.h> int ans,Sum; void dfs( int i, int s, int n) { if (s == Sum && n == 0) { ans++; return ; } if (i == 10 || n == 0) return ; dfs(i+1,s+i,n-1); dfs(i+1,s,n); } int main( void ) { int n; while ( scanf ( "%d %d" ,&n,&Sum) != EOF) { if (n == 0 && Sum == 0) break ; ans = 0; dfs(0,0,n); printf ( "%d\n" , ans); } return 0; } |
0 件のコメント:
コメントを投稿