[백준][Python] 2785 체인

실버 1 / 그리디, 정렬

⛓️

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

 

 

내 풀이

N = int(input())
L = sorted(list(map(int, input().split())))
ring = 0

if len(L) < 3:
    ring = 1
else:
    while len(L) > 2:
        L[0] -= 1
        if L[0] < 0:
            L.pop(0)
            L[0] -= 1
        n1 = L.pop()
        n2 = L.pop()
        L.append(n1+n2)
        ring += 1
    if L[0] > 0:
        ring += 1

print(ring)

 

 

코드 설명

 

문제가 이해가 안 됐다 ..

계속 헛다리 짚다가 결국 문제 해석을 위한 구글링 찬스

point: 가능한 한 적은 고리를 사용해야 함, 하나의 긴 체인으로 모든 체인을 묶어야 함

 

가장 효율이 좋은 방식은 하나의 고리를 열어 양쪽으로 연결하는 것이다.

 

우선 두 가지 상황으로 나누어서 생각했다.

1. 체인의 개수가 3 미만(2개)인 경우

2. 체인의 개수가 3 이상인 경우

 

상황 1.

if len(L) < 3:
    ring = 1

 

1번의 경우, 무조건 답은 1이다.

체인의 개수가 2개라면 고리 하나를 열어서 둘을 연결하면 된다.

 

상황 2.

else:
    while len(L) > 2:
        L[0] -= 1
        if L[0] < 0:
            L.pop(0)
            L[0] -= 1
        n1 = L.pop()
        n2 = L.pop()
        L.append(n1+n2)
        ring += 1
    if L[0] > 0:
        ring += 1

 

체인의 개수가 3개 이상인 경우이다.

 

가능한 한 적은 고리를 사용하여 하나의 긴 체인을 만들어야 한다. 체인의 길이를 입력받을 때 오름차순 정렬을 해주었다.

맨 앞에 있는 가장 적은 길이의 체인을 사용해 뒤에서부터 역순으로 연결해 주는 방식으로 진행했다.

연결 => 두 숫자를 합쳐주는 방식으로 구현했다.

 

✔️ 맨 앞에서 고리를 가져와(-1) 맨 끝의 두 체인을 연결한다. (맨 끝의 두 숫자를 합친다.) 이때, 맨 끝의 두 숫자(체인)를 pop()으로 삭제시켜 준 뒤, 두 숫자를 더한 값을 추가해 준다.

✔️ 만약 맨 앞 체인의 고리가 다 떨어졌다면 pop(0)을 통해 해당 체인을 없애준 후, 그다음 체인으로 진행한다.

✔️ 위의 과정을 체인이 2개 남을 때까지 반복한다.

✔️ 반복문이 끝나고 나서, 맨 앞의 값이 0이라면 고리를 다 쓴 것이니 연결해 줄 필요가 없다. 양의 정수인 경우에만 추가로 연결해 준다.