(JAVA) 백준 2565번 : 전깃줄 --- [DP, LIS]

www.acmicpc.net/problem/2565

2565번: 전깃줄

 

안녕하세요.

 

DP와 LIS 알고리즘을 사용하여 해결한 문제입니다.

 

 

LIS 알고리즘은 기억하시나요?

 

이는 증가하는 부분 수열 알고리즘 입니다.

 

뭐.. 이를 응용해서 길이나, 수열의 최댓값/최솟값 등을 구할 수 있죠.

 

 

아무튼

 

이 문제를 푼 지 조금 오래되서 풀이법이 가물가물 하지만 최대한 복기해가며 적어보겠습니다.

 

우선, 아래 포스팅의 문제와 비슷한 풀이방법입니다.

maivve.tistory.com/234

(JAVA) 백준 12015번 : 가장 긴 증가하는 부분 수열 2 --- [이분탐색, DP, LIS]

 

 

즉,

문제에서 구하고자 하는 값 : 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수

 

 

좀 더 생각해보면, 

 

왼쪽 전봇대와 연결된 오른쪽 전봇대의 값이 작으면 작을수록 전깃줄을 덜 없앨 수 있습니다.

 

백준 문제 예시 그림

 

입력 값

 

8

1 8

3 9

2 2

4 1

6 4

10 10

9 7

7 6

 

이 있다고 할 때

 

 

 

  1)  전깃줄의 최대 개수, 전봇대의 최대 개수를 가지는 int 배열을 생성합니다.

 

  2)  전봇대 배열을 순회하며, 전깃줄이 연결된 전봇대만 다음 알고리즘 과정을 진행합니다.

 

  3)  dp의 가장 오른쪽의 값과 현재 연결된 전봇대 번호와 비교해서, 전봇대 번호가 더 크다면 dp 가장 오른쪽에 추가합니다.

 

  3-1)  전봇대 번호가 더 작다면, dp 배열을 이분탐색합니다. 이 때, 현재 연결된 전봇대 번호와 dp 내 저장된 전봇대 번호를 비교합니다.

 

  3-2)  이렇게 해서 나온 dp의 값을 현재 전봇대 번호로 교체합니다.

 

  4)  이렇게 모든 전봇대를 순회한 후 나온 dp 배열은 증가하는 부분 수열이 되고(단, 정확히 부분 수열과 일치하지는 않을 수 있습니다!) , 해당 배열의 길이는 증가하는 부분 수열의 길이가 됩니다.

 

이 길이는 곧 모든 교차의 가능성을 제외했을 때 가장 많이 연결된 전깃줄의 개수가 됩니다.

 

 

그래서 전체 개수 - dp 배열의 길이 가 곧 정답이 되는 셈이죠!!

 

 

 

이상입니다.

 

감사합니다!

 

 

소스코드

---