길이가 일정한 성냥개비 N개가 주어질 때 이를 이용하여 만들수 있는 삼각형의 개수를 구하는 문제인​​

" jungol 1109 삼각형 만들기" 문제를 비교적 쉽게 해결한 정원이가 조금 더 어려운 문제를 풀려고 한다.

성냥개비의 개수가 1 ~ 2,000,000개 일때 해법은 어떻게 될까?

 

정원이와 함께 문제를 풀어보자.

 

[제약 사항]

1. 주어진 N개의 성냥개비를 모두 사용해야만 한다.

2. 만들어진 삼각형을 회전하거나 뒤집었을때 이전의 모양과 같다면 한 가지 경우로 본다.

3. 문제당 5개의 테스트 케이스가 주어진다.

5개의 행에 성냥개비의 수 N이 주어진다. (1 <= N <= 2,000,000)

5개의 행에 입력 순서에 맞추어 답을 출력한다.

5
17
123
5138
923456

1
8
331
549980
17766062165