[정렬 및 탐색] 백준 2785 (파이썬)

 

 

문제가 뭔소린지 처음에 모를 수도 있지만 

계속 읽다보면 이해가 간다.

 

결국 각자 갯수가 다르게 연결된 여러가지 체인들중에서 하나의 체인을 전부 해체해 다른 체인들을 연결하면서 최소한으로 연결을 하는 것이다.

 

즉, 예를 들어 3, 4, 5, 7, 9 의 체인이 주어졌을 때 

- 3인 체인을 해체해 그 3개의 고리를 만들어 4, 5, 7, 9를 연결해준다면? 고리 3개만 필요할 것이다.

- 하지만 그렇게 하지않고 3, 4, 5, 7, 9를 정직하게 연결해준다면 고리 4개가 필요할 것이다. 

필요한 고리의 최소 개수를 출력한다는 것은 이렇게 체인 하나를 모두 해체해서 남은 체인들의 고리가 되어줬을 때 성립할 수 있다.

 

 

 

내 풀이

1) 먼저 입력받은 체인들을 sort해서 오름차순으로 만들어 준다.

- 작은 것부터 해체해야 최대한 많은 체인을 해체해서 고리로 쓸 수 있다.

 

2) 해체할 체인의 인덱스를 가리키는 spot, 해체 후 생성 된 고리를 오른쪽 긴 체인부터 연결한 후 그만큼 이동한 인덱스 right 변수를 만든다.

 

3) while문을 통해 해체한 고리의 갯수가 앞으로 필요한 고리의 갯수보다 많을 때 break

- 연결하고 나면 고리가 남게 될텐데 남은 거는 또 연결해야 해서 고리가 필요하다. 그래서 그냥 남은 체인끼리 연결하고 while문을 탈출하면 된다.

 

from sys import stdin

n = int(input())
numbers = sorted(list(map(int, stdin.readline().split())))

spot = 0
right = n - 1
cnt = 0
while True:
    if right - numbers[spot] > spot:
        cnt += numbers[spot]
        right -= numbers[spot]
        spot += 1
    else:
        cnt += (right - spot)
        break

print(cnt)