POJ 2876 - Cantoring Along

http://poj.org/problem?id=2876

概要

オーダーが $N$ のカントール集合を答える．

オーダーが $N$ のカントール集合は以下の手順によって作られる．

1. $3 ^ N$ 個の - を並べて1つの線を作る
2. 各線について，3等分した中央の線を空白に置き換えて線を2つに分ける
3. 各線が1つの - になるまで 2 を繰り返す

制約

• $0 \le N \le 12$

解法

オーダー $N$ のカントール集合はオーダー $N+1$ のカントール集合の部分構造になっていることを利用して，予めオーダー12までの全集合を生成しておいて答える．

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6   string dp[13];
 7   dp[0] = "-";
 8   for (int i = 1; i <= 12; i++) {
 9     dp[i] = dp[i-1] + string(dp[i-1].size(), ' ') + dp[i-1];
10   }
11   int N;
12   while (cin >> N) {
13     cout << dp[N] << endl;
14   }
15   return 0;
16 }