[BOJ 2785] 체인

문제

체인

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

 

 

풀이

설명

필요한 고리의 최소 개수를 구하는 문제입니다.

 

방법은 다음과 같습니다.

1. 체인을 길이를 기준으로 내림차순으로 정렬합니다.
2. 가장 오른쪽 체인(가장 길이가 작은 체인)에서 고리를 하나씩 풀어 가장 왼쪽의 체인 두 개를 연결합니다.
3. 모든 체인이 연결될 때까지 2번을 반복합니다.

 

예시 코드

function solution() {
  const N = Number(input());
  const chains = input()
    .split(" ")
    .map(Number)
    .sort((a, b) => b - a);
  let left = 0,
    right = N - 1;
  let answer = 0;

  while (left < right) {
    left++;
    answer++;
    chains[right]--;
    if (chains[right] === 0) right--;
  }

  return answer;
}