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