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

C++競プロ学習日記(仮)

( 学習記録であり解説Blogではないです )

Sum of Integers|AOJ|深さ優先探索(DFS)

深さ優先探索(DFS)を勉強中で、DFSを使って解ける優しめ問題という事で、
整数の和 | Aizu Online Judge を解きました。

<題意>
0 〜 9 の数字から異なる数をN個取り出して、和がSとなる組み合わせが何個あるか出力する

#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
// i --> 0 - 9までの数字
// sum --> 合計値
// cnt --> 和がSとなる組み合わせの数
// total --> 足す数(N個まで足す)
int N, S, cnt;
void dfs( int i, int sum, int total )
{
    //N回を満たしている 且つ 合計がSに達したものをcountする
    if( total == N && sum == S )
    {
        cnt++;
        return;
    }
    //0-9まで探索したら or 足す回数がN回に達したら 終わり
    if( i == 10 || total == N ) return;
    
    //合計に i を足す場合 -> 足す回数を +1 する
    dfs( i + 1, sum + i, total + 1 );
    //合計に i を足さない場合
    dfs( i + 1, sum, total );
}
int main()
{
    while( cin >> N >> S )
    {
        if( N == 0 && S == 0 ) break;
        //合計値の初期化
        cnt = 0;
        //dfs( 数字の0から, 合計値0から, 足す数字0から)
        dfs( 0, 0, 0 );
        cout << cnt << endl;
    }
    return 0;
}

DFSを本で勉強したのですが、さっぱり実装出来る気がしなくて、
処理をいくつかに分割して書いてやっとまとまりました。
手順としては下記の工程を経ています。

1)足し算部分の再帰を書く
2)合計を取る部分を書く
3)合計がSとなったものをcountする部分を書く
4)合計に足す場合と、足さない場合を書く
5)N個だけ選んで和を取る部分を書く

個々の処理がどうなっているか良く解ったので理解が進みました。

この問題を解く際、グローバル変数に count と云う変数名を使ったら gccに怒られました。
std::count と区別がつかないよって事らしいです。
それから、returnで何も返さない関数はvoidで宣言する様で、そこも新たに覚えました。
(何も返さない関数を初めて書きました...!)

次はstack編も覚えなくてはみたいな感じです。