[BOJ] 1365. 꼬인 전깃줄

백준 문제 주소:

www.acmicpc.net/problem/1365

1365번: 꼬인 전깃줄

문제 : 전깃줄이 겹치지 않게 하는 최대 갯수는?

⊙ 최장 증가 수열
⊙ 메모이제이션(다이나믹 프로그래밍 - DP)
⊙ 이분탐색

메모이제이션과 다이나믹 프로그래밍의 차이점을 잘 모르겠다..

이거도 공부해봐야지!

아무튼 저 위의 3개를 딱 써서 하면 풀리는 문제이다.

코드 :

import sys, bisect

N = int(input())
arr = [0] + list(map(int, sys.stdin.readline().split()))
k = 0
result = [arr[1]]
for i in range(2, N+1):
    if result[k] < arr[i]:
        k += 1
        result.append(arr[i])
    else:
        result[bisect.bisect_left(result, arr[i])] = arr[i]

print(N-k-1)

 

풀이 :

리스트로 입력 받아서 앞의 전기줄의 도착지점이 더 크다면 result에 추가한다.

하지만 작다면 arr[i]보다 작거나 같은 수 중 제일 큰 수의 인덱스에 arr[i]를 집어넣는다.

즉, 1 5 10 의 result에서 arr[i]가 3이라면 1 5 10 -> 1 3 10 이 되는 것이다.

이렇게 하면 1 5 10 3 에서 results는 1 3 10 이라는 말도 안되는 순서의 배열이 나오게 된다.

하지만 그전에 1 5 10이라는 배열의 최대 갯수가 3으로 정해졌기에 바껴도 답은 상관이 없다.

그러므로 이 result의 배열은 각 자리의 배열 요소까지 구하라면 절대 답은 될 수 없지만,

그 최장증가수열 배열의 길이만 구하는 것에는 답이 가능하다.

추가로, bisect 모듈을 사용하면 매우 쉽게 이분탐색을 구현할 수 있다.