백준 1198번: 삼각형으로 자르기 (파이썬, 완전탐색)

완전탐색 알고리즘으로 최댓값을 구하기 위해 꼭지점을 하나씩 지워가며 그 값들을 배열에 넣고, max함수를 이용해서 최댓값을 구하였다.

 

삼각형의 넓이는 꼭지점들이 주어지므로 꼭지점 공식을 이용하였다.

N각형에서 나올수 있는 삼각형의 경우의 수(갯수)는 nC3이므로 n(n-1)(n-2)/6이다.

완전탐색으로 풀기 위하여 N각형에서 시계방향으로 점을 하나씩 지워가며 계산하였다.

오각형을 예시로 들자면 다음과 같다.

물론 완전탐색문제는 파이썬 library인 combination을 이용하여 풀수도 있다. 완전탐색이나 조합이나 가능한 모든 경우의 수를 구하는 것이기 때문이다.

 

조합을 이용하여 푼 풀이는 다음과 같다.

from itertools import combinations
import sys


def triangle_area(x, y, z):
    return abs((x[0]*y[1]+y[0]*z[1]+z[0]*x[1]-x[1]*y[0]-y[1]*z[0]-z[1]*x[0]))/2


jum = []
max_area = []
a = []
inp = sys.stdin.readline()

for i in range(int(inp)):
    inpp = sys.stdin.readline()
    jum.append(list(map(int, inpp.split())))

jum_list = list(combinations(jum, 3))
for k in range(len(jum_list)):
    max_area.append(triangle_area(jum_list[k][0], jum_list[k][1], jum_list[k][2]))
print(max(max_area))