ALDS1_5_A 総当たりをC++で解いてみた[AIZU ONLINE JUDGE]

AIZU ONLINE JUDGE

こんにちは! mnbd(@mnbbbbbd)です。

プログラミング初心者なので、もっといい回答があるに違いありません。

あくまでも「動作はする」サンプルとしてご覧ください。

問題文

長さ n の数列 A と整数 m に対して、A の要素の中のいくつかの要素を足しあわせて m が作れるかどうかを判定するプログラムを作成してください。A の各要素は1度だけ使うことができます。

数列 A が与えられたうえで、質問として q 個の mi が与えれるので、それぞれについて “yes” または “no” と出力してください。

入力
1行目に n、2行目に A を表す n 個の整数、3行目に q、4行目に q 個の整数 mi が与えられます。

出力
各質問について $A$ の要素を足しあわせて $m_i$ を作ることができれば yes と、できなければ no と出力してください。

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/5/ALDS1_5_A

解答

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
	cin >> n;
    int A[n];
	for (int i = 0; i < n; i++) {
		cin >> A[i];
	}
    int q;
	cin >> q;
    int const result_table_size = 2001;
    char result_table[result_table_size];

    for(int i = 0; i < result_table_size; i++) {
        result_table[i] = 'n';
    }

	for (int bits = 1; bits < (1 << n); bits++) {
		int sum = 0;
		for (int i = 0; i < n; i++) {
			int mask = 1 << i;
			if (bits & mask) {
				sum += A[i];
				result_table[sum] = 'y';
			}
		}
	}

	int tmp;
	for (int i = 0; i < q; i++) {
		cin >> tmp;
		if (result_table[tmp] == 'y') {
			cout << "yes" << endl;
		}
		else {
			cout << "no" << endl;
		}
	}
	return 0;
}

感想

配列の数が少ないので、総当たりで計算できました。

全探索のアルゴリズムを知っていれば解きやすいかもしれませんが、知らないとまったくわからないかと思います。

問題のページの一般解説には再帰関数を利用した解き方が載っていますが、個人的によくわからずに断念してしまいました。

まとめ

AIZU ONLINE JUDGEの「ALDS1_5_A 総当たり」を解いてみましたので、その回答と解説をご紹介いたしました。

少しずつですが、プログラミングの勉強をしています。
まだ初心者ですが、よかったらつながっていただけると嬉しいです。
Twitterアカウント(@mnbbbbbd

以上です。
読んでいただきありがとうございました!