문제
N개의 체인 조각을 하나로 연결할 때, 열어야 하는 최소 고리 수를 구하라.
입력
체인 조각 수 N과 각 조각의 고리 수가 주어진다.
출력
최소로 열어야 하는 고리 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 5 3 2 | 2 |
풀이
가장 짧은 체인을 분해하여 나머지를 연결한다.
- 체인을 오름차순 정렬한다
- 가장 짧은 체인부터 고리를 하나씩 열어 다른 조각을 연결한다
- 열린 고리 + 남은 체인 수가 전체 조각 수 이상이면 종료한다
핵심 아이디어: 짧은 체인을 풀어 연결 재료로 사용하면 열어야 하는 고리가 최소화된다.
코드
import sys
input = sys.stdin.readline
def getChainCount(chains, N):
chains.sort()
count = N
tied = 1
for chain in chains:
if tied + chain >= count:
break
else:
tied += chain
count -= 1
return count - 1
if __name__ == "__main__":
N = int(input())
chains = list(map(int, input().split()))
print(getChainCount(chains, N))복잡도
- 시간: O(N log N)
- 공간: O(N)