蟻本の問題をGo言語で解いてみた(p21 三角形)

問題: 三角形

n本の棒があります。棒iの長さはaiです。
あなたは、それらの棒から3本を選んでできるだけ周長の長い三角形を作ろうと考えています。
最大の周長を求めなさい。
ただし、三角形が作れない際には0を答えとしなさい。

制約

• 3 <= n <= 100
• 1 <= ai <= 10^6

解法

3辺で三角形が作れる必要十分条件は、最も長い辺の長さ < 他の2本の辺の長さの和が成り立つ事である。
これを利用して、全ての3辺の全ての組み合わせをチェックし、三角形が成立する組を探索する(他にn log nで解ける解き方もある)。
具体的な実装としてはは、3辺の組み合わせを3重ループでチェックし、
三角形が成立した場合は、すでに発見済みの周長の値と比較し、大きい方を答えの変数に保持する。

解答

package main

import (
  "fmt"
  "math"
)

func main() {
  // 入力パターン1: 答えは12
  n := 5
  a := [5]float64{2, 3, 4, 5, 10}
  fmt.Println(solve(n, a))

  // 入力パターン2: 答えは0
  n = 4
  a = [5]float64{4, 5, 10, 20}
  fmt.Println(solve(n, a))
}

// 解答
func solve(n int, a[5]float64)float64{
  var answer float64 = 0

  for i := 0; i < n; i++ {
    for j := i+1; j < n; j++ {
      for k := j+1; k < n; k++ {
        // ある組の周長
        sum_len := a[i] + a[j] + a[k]
        // 最長の辺
        max_len := math.Max(a[i], math.Max(a[j], a[k]))
        // 最長の辺以外の2辺の長さの和
        rest_len := sum_len - max_len

        // 最長の辺の長さが他の2辺の長さの和より小さい場合は、三角形が成立する
        if max_len < rest_len{
　　　　　　// すでに保持されている周長より、大きい場合は答えを更新する
          answer = math.Max(answer, sum_len)
        } 
      }
    }
  }

  return answer
}

参考文献

• p21, プログラミングコンテストチャレンジブック