백준 2785번 체인 Python

백준 2785번 체인 Python

문제설명

문제

N개의 체인이 주어집니다. 각 체인은 여러 개의 고리로 이루어져 있으며, 고리를 열고 닫아서 다른 체인과 연결할 수 있습니다. 고리를 한 번 열고 닫는 것을 비용 1로 계산할 때, 최소한의 비용으로 N개의 모든 체인을 하나의 긴 체인으로 연결하는 문제입니다.

---

테스트케이스

입력 1
체인 개수(N)	2
각 체인의 길이	3 3
출력	1

입력 2
체인 개수(N)	3
각 체인의 길이	1 1 1
출력	1

입력 3
체인 개수(N)	5
각 체인의 길이	4 3 5 7 9
출력	3

---

작동원리

이 문제의 핵심은 왜 정답이 단순히 N-1이 아닌지 이해하는 것입니다. 5개의 체인을 연결하려면 4번의 연결이 필요하니 답이 4일 것 같지만, 실제 답은 3입니다. 그 이유는 가장 짧은 체인을 '희생'시켜 연결고리로 사용하면 이득을 보기 때문입니다.

가장 쉬운 예시: [1, 1, 1] 케이스 (정답: 1)

세 개의 체인(A, B, C)을 연결하려면 2번의 연결이 필요합니다. 만약 A의 고리를 열어(비용 1) B와 C를 연결하면 어떻게 될까요? A는 길이가 1이라 통째로 연결고리가 되어 사라지고, B와 C는 하나로 합쳐집니다. 결국 비용 1만으로 3개의 체인이 순식간에 1개가 되었습니다. 이것이 바로 '보너스'의 개념입니다. 체인 하나를 완전히 소모시켜 연결 횟수를 아낀 것입니다.

핵심 예시: [3, 4, 5, 7, 9] 케이스 (정답: 3)

5개의 체인을 연결하려면 총 4번의 연결(left=4)이 필요합니다.

• 첫 번째 연결: 가장 짧은 3체인에서 고리를 하나 뺍니다. (비용 1, 남은 연결 3)
• 두 번째 연결: 또다시 가장 짧은 (이제 2가 된) 체인에서 고리를 뺍니다. (비용 2, 남은 연결 2)
• 세 번째 연결: 이제 가장 짧은 체인은 길이가 1입니다. 여기서 고리를 뺍니다. (비용 3, 남은 연결 1)

보너스 발생! 방금 고리를 뺀 체인의 길이가 0이 되어 사라졌습니다. 이 덕분에 우리가 해야 할 연결 횟수가 저절로 1 줄어듭니다. (남은 연결 0)

결과적으로 비용 3을 소모했을 뿐인데, 필요한 연결 4회를 모두 마쳤습니다. 이처럼 항상 가장 짧은 체인을 먼저 희생시키는 전략이 최소 비용을 만드는 비결입니다.

---

아이디어

• 체인의 개수 N과 각 체인의 길이를 입력받습니다.
• 가장 짧은 체인부터 사용하기 위해 입력받은 체인 길이 배열을 오름차순으로 정렬합니다.
• 필요한 연결 횟수를 저장할 변수 left (N-1로 초기화), 총비용을 저장할 cnt (0으로 초기화), 사용할 가장 짧은 체인의 인덱스 i (0으로 초기화)를 선언합니다.
• left가 0보다 클 동안, 즉 아직 연결할 체인이 남았을 동안 while문을 반복합니다.
• 루프마다 고리 하나를 열어 연결 작업을 수행합니다. 따라서 cnt를 1 증가시키고, 필요한 연결 횟수 left를 1 감소시키며, 현재 가장 짧은 체인 arr[i]의 길이를 1 줄입니다.
• 만약 arr[i]의 길이가 0이 되었다면, 체인 하나가 완전히 소모된 것입니다. 이는 연결 한번을 '공짜'로 더 한 것과 같으므로 left를 1 추가로 감소시키고, 다음으로 짧은 체인을 사용하기 위해 i를 1 증가시킵니다.
• while문이 끝나면 cnt에 저장된 값이 최소 비용이므로 이를 출력합니다.

---

전체코드

Python

N=int(input())
arr=list(map(int,input().split()))
arr.sort()

left=N-1
i=0
cnt=0

while(left>0):
    left-=1
    arr[i]-=1
    cnt+=1
    if(arr[i]==0):
        left-=1
        i+=1
print(cnt)

---

개별코드 설명

arr.sort()

탐욕 알고리즘을 적용하기 위한 가장 중요한 전처리 과정입니다. 항상 가장 짧은 체인에서 고리를 빼내기 위해 길이를 오름차순으로 정렬합니다.

left = N-1

N개의 체인을 하나로 묶기 위해 필요한 총 연결 횟수를 저장하는 변수입니다.

while(left > 0):

필요한 연결 횟수가 남아있는 동안 루프를 계속 진행합니다.

left-=1
arr[i]-=1
cnt+=1

루프의 핵심 동작입니다. 고리 하나를 열어(cnt++) 연결 작업을 한 번 수행했으니(left--), 그 고리는 가장 짧은 체인(arr[i])에서 가져옵니다.

if(arr[i]==0):
left-=1
i+=1

이 문제의 '킥'이 되는 부분입니다. 만약 고리를 가져온 체인이 완전히 소모되었다면(길이 0), 체인 자체가 사라져 연결할 대상이 하나 줄어든 것이므로, 필요한 연결 횟수 left를 한 번 더 줄여줍니다. 그리고 다음 루프부터는 그다음으로 짧았던 체인을 사용하기 위해 i를 증가시킵니다.

---

결론

이 문제는 탐욕 알고리즘(Greedy Algorithm)을 이용해 최적의 해를 찾는 대표적인 예시입니다.

핵심 아이디어는 항상 가장 가치가 낮은 자원(가장 짧은 체인)을 먼저 희생시켜 효율을 극대화하는 것입니다.

단순히 N-1번의 연산 비용을 계산하는 것이 아니라, 자원 소모(체인 길이 0) 시 발생하는 '보너스'를 정확히 계산하는 것이 정답의 관건입니다.

남은 연결 횟수, 총비용, 현재 사용할 자원 인덱스와 같은 상태 변수들을 정확히 관리하고 시뮬레이션하는 능력이 중요합니다.

---