아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

삼각형 집합

면접 대비

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

요약
서로 다른 양의 정수 n개가 주어질 때, 크기가 3 이상이고 임의의 세 원소가 삼각형을 이루는 부분집합의 개수를 구한다.
난이도

보통10점 중 5점

유형
정렬, 투 포인터, 조합론, 그리디
정답자
아직 제출이 없습니다

문제

양의 정수로 이루어진 집합이 삼각형이라고 불리려면 크기가 3 이상이어야 하고, 집합에서 서로 다른 정수 세 개를 골랐을 때 그 세 정수를 변의 길이로 하는 삼각형을 만들 수 있어야 한다.

양의 정수 집합이 주어질 때, 그 집합의 삼각형 부분집합의 개수를 구하라.

입력

첫째 줄에 정수 nn (1≤n≤501 \le n \le 50)이 주어진다. 이는 집합에 들어 있는 정수의 개수이다.

다음 nn개의 줄에 각각 정수 xx (1≤x≤1091 \le x \le 10^9)가 주어진다. 이들이 집합의 원소이다. 원소는 모두 서로 다름이 보장된다.

출력

주어진 집합의 삼각형 부분집합의 개수를 한 줄에 출력한다.

예제2

  1. 예제 1

    입력
    5
    3
    1
    5
    9
    10
    
    예상 출력
    2
    
  2. 예제 2

    입력
    10
    27
    26
    17
    10
    2
    14
    1
    12
    23
    39
    
    예상 출력
    58