(Python)백준 코딩테스트 연습 - 삼각형으로 자르기(1198)

1. 문제

https://www.acmicpc.net/problem/1198

1198번: 삼각형으로 자르기

2. 풀이

import sys
input = sys.stdin.readline

# n : 다각형 점의 수
n = int(input())

# n_l : 다각형 점 좌표 리스트
n_l = []
for i in range(n):
    n_l.append(list(map(int, input().split())))
max_area = 0
def area_find(target_list, p_l, depth):
    global max_area
    if depth == 3:
        a = (((p_l[0][0] - p_l[1][0]) ** 2) + ((p_l[0][1] - p_l[1][1]) ** 2)) ** 0.5
        b = (((p_l[0][0] - p_l[2][0]) ** 2) + ((p_l[0][1] - p_l[2][1]) ** 2)) ** 0.5
        c = (((p_l[1][0] - p_l[2][0]) ** 2) + ((p_l[1][1] - p_l[2][1]) ** 2)) ** 0.5
        s = (a + b + c) / 2
        area = (s * (s - a) * (s - b) * (s - c)) ** 0.5
        max_area = max(max_area, area)
        return
    for i in range(depth, n):
        p_l.append(n_l[i])
        area_find(target_list, p_l, depth + 1)
        p_l.pop()
area_find(n_l, [], 0)
print(max_area)

3. 후기

 - 문제는 주어진 좌표들을 이용한 삼각형 중 가장 넓이가 큰 삼각형의 넓이를 출력하는 문제이다.

 삼각형의 넓이를 구하는 방법은 여러가지가 있겠지만, 해당 코드에서는 sin, cos의 관계를 이용한 넓이 공식을 사용하여 구하였다.

 문제을 해결하며 알고리즘을 해결하는 능력에 수학적인 부분이 꽤나 많은 영향을 미친다는 생각을 하게 되었다.