[홀로 하는 코딩 공부] 꼬인 전깃줄 (Python)

백준

사용 언어: Python

문제 링크: https://www.acmicpc.net/problem/1365

1365번: 꼬인 전깃줄

*** 본 문제를 푸는 과정을 공유하려 한다.

---

▶ 문제 조건이 "잘라내는 전선을 최소로 하여 꼬여 있는 전선이 하나도 없게 만든다"이다. 

▶ 두번째 줄 입력값은 왼쪽 전봇대의 번호에 따라 연결된 오른쪽 전봇대의 번호가 나열되어있다. 그 뜻은 왼쪽 전봇대와 연결된 오른쪽 전봇대의 번호가 오름차순으로 연결되어있으면 꼬이지 않는 것이다. 즉, 오른쪽 전봇대의 번호들이 길게 오름차순되도록 정렬하는 LIS알고리즘을 사용하면 된다는 생각이 들었다.

▶ LIS 알고리즘이 생각나면 거의 다 푼것이다. 이제 LIS 알고리즘 전형적인 틀을 작성해주고 문제에서 원하는 답만 확인하면된다. 찾아내야하는 답이 잘라내야하는 전선의 최소개수이기에 LIS 알고리즘을 통해 추출된 오름차순으로 정렬될 수 있는 값의 개수를 전봇대 개수에서 빼주면 된다.

• 전봇대 개수는 1보다 크거나 같아야 하기에 전봇대 번호는 0은 될 수 없기에 MIN_VALUE는 0이라고 정의하였다.
• lis_arr 배열에 비교를 위한 MIN_VALUE를 미리 추가하였기에 답(잘라내야하는 전선의 최소 개수)를 계산할때는 lis_arr배열에서 1을 빼준 값을 전봇대 개수에서 빼줘야한다. 

import sys
input = sys.stdin.readline

n = int(input())
n_list = list(map(int, input().split()))

def binary_search(arr, tgt):
    left, right = 0, len(arr)-1
    while left < right:
        mid = (left+right) // 2
        if arr[mid] < tgt:
            left = mid + 1
        else:
            right = mid
    return right

MIN_VALUE = 0
lis_arr = [MIN_VALUE]

for num in n_list:
    if lis_arr[-1] < num:
        lis_arr.append(num)
    else:
        idx = binary_search(lis_arr, num)
        lis_arr[idx] = num
print(len(n_list) - len(lis_arr) + 1)

 

 

▶ 문제에서 LIS 형태가 보이니 쉽게 풀렸다.  앞으로도 문제를 풀 때, 문제에서 어떤 알고리즘을 써야할 것인지 아는 순간까지만 도달하면 그 후에는 쉽게 풀릴 것같다. 그 수준 까지 도달하기 위해서는 다양한 알고리즘에 많이 익숙해져야겠다는 생각이 들었다.

---

>> 위 내용은 필자가 코딩테스트 문제를 푼 코드입니다.

>> 부족한 점이 많을 수 있기에 잘못된 내용이나 궁금한 사항이 있으면 댓글 달아주시기 바랍니다.

>> 긴 글 읽어주셔서 감사합니다.