소스 코드 : https://github.com/CaChiJ/JustCodes/blob/main/Algorithm%20Solutions/DP/BOJ1365.cpp
👀 살펴보기
문제에서는 다음과 같이 전봇대와 전봇대의 쌍이 주어진다. 주목할 점은 모든 전봇대가 단 1개의 맞은편 전봇대와 연결된다는 점이다. 즉, 연결 정보를 배열에 저장할 때 한쪽의 전봇대 번호를 배열의 인덱스로, 나머지 한쪽은 배열 요소의 값으로 표현할 수 있음을 알 수 있다.
예를 들어 문제 설명에 나온 위 그림은 다음과 같이 표현할 수 있다. 편의상 시작 인덱스를 1로 하였다.
우리는 이 배열의 요소들 중 임의의 요소를 제거하여 배열의 크기가 가장 크면서 요소의 값이 증가하도록 만들어야 한다. 바꿔 말하면 이 배열에서 가장 긴 증가하는 부분수열(LIS)을 찾으면 된다. (그리고 전봇대의 개수) - (LIS의 크기) 로 답을 구할 수 있다.
🧶 로직
전봇대의 개수 은 1보다 크고 100,000보다 작다. 따라서 의 LIS로 답을 구할 수 있다. 위 👀살펴보기에서 나온 방식으로 입력값을 잘 저장해두었다면 구현은 일반적인 LIS문제와 다를 바 없기 때문에 별도로 설명하지 않겠다. LIS를 얻은 뒤에는 그 크기를 통해 제거해야 하는 전봇대 개수를 구해 출력하면 된다.
⏱ 시간복잡도
시간복잡도는 이다.
