문제 2785 체인

Sungmin·2023년 5월 12일
0

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)

배운점

풀이정리

  1. chain리스트를 오름차순 정렬
  2. cntx를 초기화
    [cnt를 1로 초기화한 이유는 고리하나당 2개를 연결할 수 있기 때문]
  3. 0번째 인덱스부터 체인개수 하나 제거
  4. 사용한 체인개수 증가
  5. 만약 [x]번째 체인을 다 사용하면 인덱스 증가
  6. 사용한 체인개수와 다 사용한 인덱스의 합이 n보다 크거나 같으면 break!!

의외로 고려해야할 부분이 많아서 생각하는데 시간이 오래걸린 문제이다. 구현문제는 자주 풀어야 빨라지는것 같다.

profile
Let's Coding

0개의 댓글