2565

백준 2565 풀이 (전깃줄, 다이나믹 프로그래밍, LIS)

이번 문제는 코드를 다 짜서 돌렸는데 잘나오길래 고렇게 했더니 하도 안나와서 LIS를 다시 적용해서 풀게된 문제이다. 다음과 같은 그림이 존재하는 경우 겹치는 선을 제거하여 몇개의 선을 최소로 제거해야 겹치지 않게 되는지 구하는 문제였다. 처음에는 각 연결별로 겹치는 부분을 구하고 가장 겹치는 선이 많은 줄을 하나씩 제거하여 제거되는 선을 찾으려고 했다. 1. 각 라인별로 겹치는 선을 찾는다. 2. 최댓값을 구하고 해당 인덱스를 찾는다. 3. 해당 인덱스를 제거하는 경우 다른 라인들과의 겹치는 선을 갱신한다. 4. 만약 모든 값이 0이하인 경우, 몇개의 라인을 없앴는지 확인한다. line 1,8 3,9 2,2 4,1 6,4 10,10 9,7 7,6 cross 5 4 2 3 2 0 2 2 x 4 1 2 1..