[백준] 1365번 '꼬인 전깃줄' - Python

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

1365번: 꼬인 전깃줄

---

문제

---

풀이

import sys
input = sys.stdin.readline

n = int(input().rstrip())
pole = list(map(int, input().rstrip().split()))

def binary_search(left, right, target):
    while left < right:
        mid = (left + right) // 2
        if list[mid] < target:
            left = mid + 1
        else:
            right = mid
    return right

list = []
list.append(pole[0])
for i in range(1, n):
    if list[-1] < pole[i]:
        list.append(pole[i])
    else:
        a = binary_search(0, len(list)-1, pole[i])
        list[a] = pole[i]
print(n - len(list))

 

LIS 알고리즘을 이용하는 이진탐색 코드입니다.

 

 

Try : 일차함수를 이용해서 하려고 했는데 시간 복잡도에서 O(n^2)가 나와서 초과 됐습니다.

import sys
input = sys.stdin.readline

n = int(input().rstrip())
pole = list(map(int, input().rstrip().split()))

def linear_function(x_intercept, y_intercept):
    a = -(y_intercept / x_intercept)
    b = y_intercept
    list = []
    list.append(a)
    list.append(b)
    return list

def find_conatct(a1, b1, a2, b2):
    a = a1 - a2
    b = b2 - b1
    if a / b > 0:
        return True
    else:
        return False
    
linear = [[0] for _ in range(n)]
for i in range(n):
    linear.append(linear_function((i+1), pole[i]))
    print(linear[i])

contact = [0 for _ in range(n)]
for i in range(n):
    for j in range(n):
        if i!=j:
            if find_conatct(linear[i][0], linear[i][1], linear[j][0], linear[j][1]):
                contact[i] += 1

min_contact = min(contact)
print(min_contact)