피타고라스 수

시간 제한2초메모리 제한512 MB

요약

막대기 길이 N개가 주어질 때, 서로 겹치지 않는 두 막대로 원시 피타고라스 삼조의 두 변을 이루는 쌍을 최대한 많이 만든다.

난이도: 보통10점 중 7점
유형: 그래프, 수학, 정수론, 백트래킹
정답자: 아직 제출이 없습니다

문제

피타고라스 수 $(a, b, c)$ 는 다음 조건을 모두 만족하는 세 수의 쌍이다.

$a$ , $b$ , $c$ 는 정수이다.
$a^2 + b^2 = c^2$
$a$ 와 $b$ 의 최대공약수는 1이다.

영선이는 나무 막대 $N$ 개를 가지고 있고, 직각삼각형 모양의 장난감을 최대한 많이 만들려고 한다. 장난감 하나의 세 변 길이 $(a, b, c)$ 는 피타고라스 수여야 하며, 두 변 $a$ 와 $b$ 는 나무 막대로, 나머지 한 변 $c$ 는 쇠 막대로 만든다. 한 장난감에 쓴 나무 막대는 다른 장난감에 다시 쓸 수 없다. 영선이는 쇠 막대를 아주 많이 가지고 있어서 쇠 막대가 모자랄 일은 없다.

만들 수 있는 장난감의 최대 개수를 구하시오.

입력

첫째 줄에 나무 막대의 개수 $N$ ( $1 \le N \le 200$ )이 주어진다.

둘째 줄에 나무 막대 $N$ 개의 길이가 공백으로 구분되어 주어진다. 각 길이는 1,000,000보다 작은 자연수이다.

출력

첫째 줄에 만들 수 있는 장난감의 최대 개수를 출력한다.

예제3

예제 1
입력
```
9
3 4 4 3 11 5 12 9 4
```
예상 출력
```
3
```
예제 2
입력
```
4
20 21 3021 220
```
예상 출력
```
2
```
예제 3
입력
```
5
28 195 1035 21412 37995
```
예상 출력
```
2
```