📚 2785 - 체인

체인

이해

이 문제는 이해하는 데에 어려운 것 같다.

두 번째 줄에 입력된 것이 체인의 길이라고 하는데, 이는 체인을 연결한 고리의 수를 의미한다.

6
3 4 5 7 9 11

고리수 : 0

3일 때
- 연결한 고리수 += 3
- 현재 연결한 가능한 고리수 3개이므로, (4-5, 5-7, 7-9, 11)


4일 때 (3, 4 체인 고리수로 변경됨)
- 연결한 고리수 += 4
- 현재 연결한 가능한 고리수 7개이므로, (5-7, 7-9, 9-11)

연결 가능한 고리 수가 아직 연결되지 않은 고리 수 보다 많다.
그러므로 결과는 4가(연결되지 않은 고리 수) 된다.

소스

import sys  
  
read = sys.stdin.readline  
  
n = int(read())  
  
chain = list(map(int, read().split()))  
  
chain.sort()  
  
s = 0  
answer = 0  
for i in range(len(chain)):  
    # 남아있는 체인의 개수  
    cnt = n - i - 1  
  
    # 현재 만들 수 있는 체인의 길이를 더해준다.  
    # 체인 길이 : 고리  
    # 고리의 수를 늘려가며, 남아있는 체인을 묶어준다.  
    s += chain[i]  
	
	
    if s >= cnt:  
        print(s)  
        answer = cnt  
        break  
  
print(answer)

참고 : http://wookje.dance/2017/09/03/boj-2785-%EC%B2%B4%EC%9D%B8/