よくあるCの練習問題っぽいけど、台形になったとたんにややこしくなった感!
問題
N個のレンガ(*)を全部使ってピラミッドを作る。
例えばN = 1なら、こう。
*
N=6ならこう。
*
**
***
N=7の場合なら、
***
****
こんな感じ、と。
どうしようか
一発で解決する方法を思いつかなかったので、高さから攻める事にした。
台形の上底をa、高さをh、与えられるブロック数をNとする。
等差数列の和の公式を使うと、こう。
高さhから上底aを求めたいのでわちゃわちゃと変形するとこうなる。
hの値を変えて突っ込むとaの値が求まるので、最も大きいhの値を調べればいい。
ただし、aは自然数の範囲。
ちょっと面白い部分
これ、出力を見てみるとh=2の時のNが全部素数になってる。
コード
using System; using System.Linq; using System.IO; using System.Text; using System.Collections; using System.Collections.Generic; /** * Auto-generated code below aims at helping you parse * the standard input according to the problem statement. **/ class Solution { static void Main(string[] args) { int total = int.Parse(Console.ReadLine()); Console.Error.WriteLine(total); TP2 pyramid = new TP2(total); Console.WriteLine(pyramid.Draw()); } //クラス内クラス public class TP2 { private int total; private int width; private int height; //コンストラクタ public TP2(int N) { total = N; height = 1; width = N; ps(); } //台形の上底と高さを調べる private void ps() { int bt = total * 2; int ht = (total + 1) / 2; for (int h = 2; h <= ht; h++) { //高さhから上底aを計算する int a = (bt - h * h + h) / (2 * h); //上底aと高さhからサイズsを求める int s = (h * (2 * a + h - 1)) / 2; if (a > 0 & s == total) { width = a; height = h; } } } //台形を描画した文字列を返す public string Draw() { string str = ""; for (int h = 0; h < height; h++) { string tmp = ""; for (int w = 0; w < width + h; w++) { tmp += "*"; } str += tmp; if (h < height - 1) str += System.Environment.NewLine; } return str; } } }
追記
もしかしたら、こうしたらより早くなるのかもしれない。
private void ps() { int bt = total * 2; int ht = (total+1) / 2; for(int h = IntRootOf2N(); h >= 2; h--) { int a = (bt - h * h + h) / (2 * h); int s = (h * (2 * a + h - 1)) / 2; if (s == total) { width = a; height = h; break; } } } private int IntRootOf2N() { return (int)(Math.Sqrt(2 * total)); }