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

三角形作れるか問題

問題概要

入力として与えられる辺の候補より、周長が最も長い三角形を作れ
入力:辺の長さ
出力:周長
ただし、三角形を作ることができなければ0を出力せよ。

基礎知識

三角形が作れる条件は、
\[ 三角形で一番長い辺 < その他の二辺の和 \]

方法

あらかじめ辺の配列を長い順にソートしておく(n log n)
あとは大きい順に3辺とり、三角形を作れるか判定する(n)

例示

入力:{ 10,5,4,2,3}
出力:12

回答コード(C#)

class Triangle{
	public int CreateTriangle (int[] side)
	{
		Array.Sort (side);
		int ret = 0;

		for (int i = (side.Length-1); i >= 2; i--) {
         		if (side [i] < side [i - 1] + side [i - 2]) {
				ret = side [i] + side [i - 1] + side [i - 2];
				break;
			}
		}
		return ret;
	}
}

参考書籍

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?