Volume0-0030 Sum of Integers
与えられた整数sを、0~9の数字のうちn個の和で表す時の場合の数を求める問題です。
全探索すれば良いのですが、今まで全探索のプログラムを書いたことがなかったので、かなり苦戦しました。
#include<stdio.h> int A[11]={0,1,2,3,4,5,6,7,8,9,0}; int cnt=0; void dfs(int i,int rest,int d,int n){ if(i<11){ if(d==n){ if(rest==0){cnt++;return;} else return; } if(rest<0)return;/*sを超える*/ dfs(i+1,rest-A[i],d+1,n);/*A[i]を選ぶ*/ dfs(i+1,rest,d,n);/*A[i]を選ばない*/ } return; } int main(){ int n,s; while(1){ scanf("%d %d",&n,&s); if(n==0 && s==0)break; if(s > 55)printf("0\n"); else { cnt=0; dfs(0,s,0,n); printf("%d\n",cnt); } } return 0; }
全探索、もっと練習します。