[파이썬/python] 백준 2785- 체인

문제

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

---

문제 설명

1. N개의 체인이 존재한다.
2. 각각의 체인은 여러 개의 고리로 이루어져 있다.
   1. 길이가 3인 체인 -> 고리가 3개인 체인
3. 체인을 분리하거나 연결하여 두 개의 체인을 하나의 긴 체인으로 변경할 수 있다.
4. 모든 체인을 하나의 체인으로 묶기 위해 필요한 최소한의 고리를 찾아라.

 

 

<예시 1>

1. 길이가 1인 체인(고리가 1개로 이루어진)이 3개가 존재한다.

 

2. 가운데 체인을 연다.

 

3. 양 끝 체인을 연결한다.

 

4. 가운데 체인을 닫는다.

---

풀이

하나의 체인을 전부 다 사용해서 체인들을 연결한다면 최종적으로 사용하는 고리의 수가 줄어들게 된다. 따라서 고리의 개수가 낮은 것부터 길이가 긴 체인끼리 묶는다면 최소한의 고리를 사용하여 모든 체인을 하나로 묶을 수 있을 것이라 생각했다.

1. 체인의 길이가 오름차순으로 정렬한다.
2. start = 첫 번째 인덱스, end = 마지막 인덱스
3. 첫 번째 체인의 길이가 0이 아니라면 고리를 하나 끊어 가장 긴 고리끼리 연결한다.
4. 체인의 길이가 0이라면 start를 1 증가시켜 그다음으로 짧은 고리를 선택한다.
5. start(제일 앞에 있는 체인)와 end(연결이 안 된 최장 체인)가 같아지면 모든 고리를 연결했다는 것이므로 반복문을 종료한다.

---

코드

import sys
input = sys.stdin.readline

N = int(input())
chains = list(map(int,input().split()))

chains.sort()
start = 0
end = N-1
cnt = 0
while start != end:
    if chains[start] > 0:
        chains[start]-=1
        end-=1
        cnt+=1
    else:
        start+=1
print(cnt)

---

시간복잡도

• 최악일 경우 체인의 개수는 $5*10^5$개
• 정렬할 때 걸리는 시간복잡도는 $nlog_2n$이므로 약 $O(5*10^5 * log_2(5*10^5))$
• $10^3(1000) = 2^{10}(1024)$이므로 $10^5*5=2^{19}$정도로 치환이 가능하다.
  따라서 정렬의 시간복잡도는 약 $O(5*10^5 * 19)=O(10^7)$이다.
• 체인의 길이는 체인의 개수 총합이 N보다 클 때 최악이다.
• start와 end가 같아질 때 까지 반복하므로 가장 작은 체인의 길이가 $5*10^5$ 보다 클 때 약 $O(5*10^5)$ 만큼의 시간복잡도가 걸린다.
• 따라서 최악일 경우 약 $O(10^7 + 5*10^5)$의 시간복잡도를 가진다.