3本の棒で三角形を作るために必要な最小の分数を求めるC++プログラム

ここに3つの整数 a、b、c があるとします。それぞれの長さが a、b、c である3本の棒があり、1分ごとに好きな棒を1本選んで長さを1cmずつ伸ばすことができます。ただし、棒を折ったり切ったりすることはできません。このとき、3本の棒で三角形を形成できるようにするために必要な最小の分数を求めます。

問題例

たとえば、入力が a = 2、b = 3、c = 5 の場合、出力は 1 になります。a または b のどちらか一方を1だけ伸ばせば、(a + b) > c という条件を満たす三角形を作ることができるためです。つまり、わずか1分で十分ということになります。

解き方・アルゴリズムの手順

三角形の成立条件より、最も短い2本の辺の和が、最も長い辺よりも大きくなければなりません。そこで、次の手順で問題を解くことができます。

配列 A = { a, b, c } を定義する
配列 A を昇順にソートする
max(A[2] - A[1] - A[0] + 1, 0) を返す

ソート後、A[2] が最長の辺となります。もし A[1] + A[0] がすでに A[2] より大きければ、追加の操作は不要なので 0 を返します。そうでなければ、条件を満たすまでに不足している「A[2] - A[1] - A[0] + 1」分の時間が必要です。

実装例

理解を深めるために、以下のC++による実装を見てみましょう。

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

int solve(int a, int b, int c) {
    vector<int> A = { a, b, c };
    sort(A.begin(), A.end());
    return max(A[2] - A[1] - A[0] + 1, 0);
}
int main() {
    int a = 2;
    int b = 3;
    int c = 5;
    cout << solve(a, b, c) << endl;
}

入力

2, 3, 5

出力

1