[Python] 백준 2785번: 체인

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

import sys
input = sys.stdin.readline


def getChainCount(chains, N):
    chains.sort()

    chainCount = N
    tiedChains = 1

    for chain in chains:
        if tiedChains + chain >= chainCount:
            break
        else:
            tiedChains += chain
            chainCount -= 1

    return chainCount-1


if __name__ == '__main__':
    N = int(input())
    chains = list(map(int, input().split()))

    chainCount = getChainCount(chains, N)
    print(chainCount)

예제 입력 3에 해당하는

5

4 3 5 7 9

의 경우, 3에 해당하는 체인을 3개로 나누어서 남은 4개의 체인을 묶어주면 3번만에 끝나게 되는데, 이러한 특성이 이 문제의 핵심이다.

 

7

2 2 100 100 100 100 100

위처럼 체인을 오름차순으로 정렬시키고 for문을 돌면서, 남아있는 체인의 개수(chainCount)와 묶여있는 체인의 개수(tiedChains)를 갱신시키면 된다. 위 예시의 경우에는, 처음에 2를 소모함으로써 100 100 100이라는 3개의 체인을 묶게 되고, 그 다음의 2를 소모함으로써 모든 체인들(100 100 100 100 100)을 다 묶게 된다.

일반적인 경우에는, 묶여있는 체인의 개수(tiedChains)에 현재 체인의 값을 그대로 더해주고 남은 체인의 개수(chainCount)를 하나 줄여주면 된다. 그리고 if tiedChains + chain >= chainCount: 라는 조건을 만족할 경우 바로 break로 탈출해주고 chainCount-1값을 리턴해주면 된다.