백준 : 21147번, Triangular Collection

문제 주소 : https://www.acmicpc.net/problem/21147

정답 비율 : 68.75% (2022.01.06 10:40 기준)

21147번: Triangular Collection

 

<< 문제 요약 >>

1. N개의 양의 정수로 이루어진 집합 R이 주어집니다. (R의 원소에는 중복된 수가 없습니다.)

2. 집합 R에서 최소 크기가 3인 부분집합 K을 선택합니다. 

3. 부분집합 K에서 모든 크기가 3인 부분집합에 대하여 "각 원소를 변으로 가지는 삼각형을 만들 수 있는가?"를 만족하는 부분집합 K의 개수를 구하시오.

 

<< 문제 풀이 >>

수학적 개념

세 변이 주어졌을 때 이를 변으로 가지는 삼각형의 존재 유무 판별법 각 변을 A, B, C라고 했을 때 아래 두 조건을 만족하면 됩니다.

1. A <= C , B <= C

2. A + B > C

 

아이디어

부분 집합 K의 가장 작은 최악의 경우에 대하여 위 조건을 만족하면 해당 부분 지합 K의 모든 크기가 3인 부분집합으로 삼각형을 만들 수 있음을 증명할 수 있습니다.

최악의 경우 : K의 두 원소의 합이(A + B)가 가장 작은 때, 나머지 변으로 K의 가장 큰 원소로 가지면 됩니다.

 

<< Python3 코드 >>

# solve 21147
import sys

n = int(input())
for i in range(n):
	arr.append(int(sys.stdin.readline())
ans = 0

for i in range(n - 2):
    for j in range(i + 1, n - 1):
        count = 0
        for k in range(j + 1, n):
            if arr[i] + arr[j] > arr[k]:
                count += 1
            else:
                break
        ans += 2 ** count - 1
print(ans)