[백준 2565번] 전깃줄- java

문제 설명

1. N개의 전깃줄이 있고, 이 전깃줄은 A전봇대와 B전봇대를 연결한다.

2. 전깃줄은 교차되는 경우가 있고, 교차되어서는 안된다.

3. 그렇기 때문에 교차되는 전깃줄을 없애주어야 한다.

4. 교차되는 전깃줄이 없도록, 전깃줄을 제거해주는 최소 개수를 return하면 된다.

 

풀이 과정

 1. DP를 통해서 진행한다. 처음에 생각하는것이 조금 어려운데 '가장 긴 증가하는 부분 수열' 문제의 알고리즘을 적용해야 한다.

 2. 위의 그림을 통해 확인해 보면, A전봇대의 숫자에 대해 오름차순으로 정렬한 후, 이곳에서 B와 연결할 때에 큰 위의 가장 긴 증가하는 부분 수열을 적용하면 교차하지 않는 전선의 개수를 구할 수 있게 된다. 그 이유에 대해 말하자면

A 처음 전봇대 기준으로 만약 1 - 8 이 연결되어 있고

B 다음 전봇대 기준으로 만약 2 - 9 이 연결되어 있다면 9는 8보다 크기 때문에 두 전봇대는 교차하지 않는다.

C 다음 전봇대 기준으로 만약 3 - 1 이 연결되어 있다면 교차되지 않는 전봇대가 없다.

D 다음 전봇대 기준으로 만약 4 -10 이 연결되어 있다면 10은 8, 9와 교차되지 않는다.

.... 이런 식으로 진행하면 결국 가장 많은 교차되지 않는 전선의 개수를 구할 수 있을 것이다.

 3. 위의 풀이를 통해, 교차하지 않는 전선의 개수를 구할 수 있게 되었다. 그렇다면 이제 전체 전선의 개수에서 이 교차되지 않는 최대 전선의 개수를 구하면? 교차되는 최소 개수를 구할 수 있을 것이다.

 4. 이제 적용하기만 하면 된다!

코드

 

참 DP는 어렵다... 처음에 풀이 방법을 구해나가는 것이 힘들고 적용할 때도 생각을 많이 해야하는 것 같다.