[BOJ-JS] 18044번 - Polygon

18044번: Polygon (acmicpc.net)

18044번: Polygon

각 테스트 케이스마다 n개의 변 길이가 주어지고, 이 변들을 사용해서 만들 수 있는 최대 둘레길이의 다각형의 둘레를 출력하는 문제.

 

아이디어는 다음과 같다.

- 제일 긴 변을 제외한 나머지 변의 길이의 합이 제일 긴 변보다 길면 삼각형을 만들 수 있다.

- 그런데 제일 긴 변을 뺀 나머지 변의 길이의 합이 긴 변의 길이보다 작거나 같다면? 긴 변을 뺀 나머지로 삼각형을 만들 수 있는지 체크해야 한다. 다시 윗 단계로.

 

처음에 전체 변 길이를 정렬할때 O(n log n)만큼의 시간이 걸린다. 여기서 '제일 긴 변을 제외한 나머지 변의 길이'를 매번 다시 계산해야 하면 여기에서 O(n^2)만큼 연산이 필요할 수 있으므로, 누적합 배열을 따로 만들어 두어서 활용하면 가장 긴 변을 제외하는 작업을 계속 해야 하더라도 O(n)으로 풀이가 가능해진다.

l=(0+require('fs').readFileSync(0)).split`
`
l.filter((e,i)=>i>0&&(i%2==0)).map(a=>{
  a=a.split` `.map(i=>+i).sort((i,j)=>i-j)
  b=[]
  s=r=0
  a.map(i=>b.push(s+=i))
  for(i=a.length-1;i>1;i--){if(a[i]<b[i-1]){r=b[i];i=0}}
  console.log(r)
})