2971. Find Polygon With the Largest Perimeter

[zeikar]

Problem link

https://leetcode.com/problems/find-polygon-with-the-largest-perimeter

Problem Summary

주어진 배열의 값의 길이의 선으로 만들 수 있는 도형의 최대 둘레를 구하는 문제.

Solution

문제에 답이 있는데

3 이상의 k에 대해서 a1 <= a2 <= a3 <= ... <= ak 이고 a1 + a2 + a3 + ... + ak-1 > ak 이면 k각형이 무조건 존재한다.

즉, 다른 모든 변의 길이의 합보다 큰 변이 없어야 한다.

정렬한 후 둘레를 하나씩 더해보면서 변의 길이보다 큰지 체크해주면 된다.

Source Code

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums.sort()

        res = -1
        perimeter = 0
        for num in nums:
            if perimeter > num:
                res = perimeter + num
            perimeter += num

        return res