문제 2785 체인

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

Solution

n = int(input())
chain = list(map(int, input().split()))
chain.sort()
cnt = 1
x = 0

while True:
    
    chain[x] -= 1
    cnt += 1
    
    if chain[x] == 0:
        x += 1
    
    if cnt + x >= n:
        break
    
print(cnt - 1)

배운점

풀이를 정리하자면

• chain리스트를 오름차순 정렬 해 준다
• 사용한 체인의 개수인 cnt와 인덱스 번호인 x를 초기화
  [cnt를 1로 초기화한 이유는 체인 한개당 두개의 체인을 연결할 수 있기때문]
• while문을 돌며 [0]번째부터 체인의 개수를 -1 해 주고
  cnt += 1
• [x]번째 인덱스의 체인을 다 사용했을 경우 x += 1
• 만약 사용한 체인개수와 사용한 인덱스개수가 n보다 크거나 같으면 break!!
• 처음 초기화할 때 cnt = 1로 했기 때문에 cnt - 1

의외로 고려해야할 부분이 많아서 생각하는데 오래걸린 문제이다.