2021/11/10

B - Making Triangleをpythonで解く

#atcoder

問題
解き方

問題

問題のリンク https://atcoder.jp/contests/abc175/tasks/abc175_b

N本の棒が与えられるので、辺の長さが異なる三角形を作ることが出来る組み合わせが何通りであるか調べるというもの。

解き方

三角形になるための条件は

2つの辺の長さを足し合わせると残りの1つの辺の長さより長くなる。
また、2の辺の長さを引いた時、残りの1つの辺の長さより短くなる。

三角形を作るための条件

とのこと。

加えて長さが全て異なる状態でないといけないので、

棒A、B、Cが
A < B < C の場合に A + B > C

である時に三角形が作れると言えそう。

棒A、B、Cを選び、A < B < C かつ A + B > Cの場合にカウントアップする。
あらかじめソートしておけばA < B < Cであるかは見なくてもよい。

N = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0
for a in range(N):
	for b in range(a + 1, N):
		if L[a] == L[b]:
			continue

		for c in range(b + 1, N):
			if L[a] == L[c] or L[b] == L[c]:
				continue

			if L[a] + L[b] > L[c]:
				ans += 1

print(ans)

ACしたもの↓
https://atcoder.jp/contests/abc175/submissions/27165280