[Python] 백준 2785_체인 : 그리디

 

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

2785번: 체인

처음에는 문제 설명 이해가 잘 안돼서.. 다른 블로그 검색해서 이해했다.. ^^ 껄껄

여러 개의 고리로 이어진 체인들의 정보가 주어지는데, 체인의 고리를 사용해서 모든 체인을 연결해야한다.

이때, 열고 닫아야하는 최소한의 고리수를 찾아야 한다.

 

풀이 방법

'최소한의 고리 수'

> 짧은 길이의 체인부터 소모하면 연결해야하는 구간을 줄일 수 있다.

> 연결해야하는 구간이 줄어들면 열고 닫아야하는 고리의 수도 최소화할 수 있다.

 

따라서, 체인들을 길이 순으로 오름차순 정렬

→ 매순간 제일 짧은 길이의 체인을 소모해서 연결 구간의 갯수를 줄이기 때문에 그리디 알고리즘 이다!

 

구간의 갯수 : 체인 갯수(n) - 1

1. 한 체인의 고리 갯수가 구간의 갯수보다 많으면
- 구간의 갯수만큼만 고리를 소모하면 됨

👉 가장 짧은 0번째 체인의 고리 2개를 소모해서

👉 연결해야하는 2개의 구간을 연결하여 하나의 체인으로 만들 수 있다.

 

2. 한 체인의 고리 갯수가 구간의 갯수와 같으면
- 다른 체인들 사이의 구간들을 모두 연결하고, 하나는 본인 체인과 나머지 체인과 연결 해야함

👉 0번째 체인의 고리 2개를 구간 2개를 연결하는데 사용

👉 나머지 하나는 본인과 1번 체인과 연결하는데 사용한다.

 

3. 한 체인의 고리 갯수가 구간의 갯수보다 작으면
- 한 체인의 고리를 모두 연결하는데 사용, 연결하는 구간은 하나 줄어들음

가장 길이가 짧은 0번째 체인을 모두 사용하여 2개의 구간을 연결, 구간 갯수를 줄인다.

- 다른 체인의 고리를 사용하여 추가로 남은 구간을 연결해야한다 (while 반복)

 

최종 코드

n = int(input())
l = list(map(int, input().split()))

# 정렬
l.sort()
answer = 0      # 소모한 체인 갯수
i = 0
cnt = n - 1     # 연결해야하는 구간

while i < len(l):
    if cnt == 0:
        break
    if l[i] >= cnt:      # l[i]의 갯수가 연결해야하는 구간과 같거나 많으면
        answer += cnt   # 구간의 갯수만큼 체인 사용
        break
    else:   # 구간의 갯수가 l[i] 보다 많거나 작으면 > l[i] 체인 모두 연결하는데 사용
        cnt -= 1        # 연결해야하는 부분 하나 감소
        cnt -= l[i]     # l[i]개 구간 연결
        answer += l[i]  # l[i]개 체인 사용
        i += 1
print(answer)

 

 

---

그리디 알고리즘이 쉬운 방식인데 은근 헷갈려서 연습 중이다. 히히