🔌 백준 2565번 : 전깃줄

서로 교차하지 않게 전깃줄을 설치할 수 있는 최대 개수를 구하는 문제

🔗 백준 2565번 - 전깃줄

---

❌ 아이디어를 떠올리지 못함

내가 제일 자신 없는 DP문제였고, 핵심 아이디어를 떠올리지 못했다.

문제 태그를 확인해 DP를 사용해야 한다는 것을 알았음에도, DP 테이블을 만들어야 한다는 것에 매몰되어 다른 아이디어를 생각하지 못했다.

---

💡 필요한 아이디어

문제에서는 **최장 증가 수열 (LIS, Longest Increasing Subsequence)**을 사용해야 한다.

슬펐던 것은, 나는 LIS 알고리즘에 대해 이미 알고 있다는 것이었다.

LIS를 구현하는 방법도 알고 있었으며, 입력 값이 많은 경우에 이진탐색을 접목하여 시간복잡도를 줄이는 방법도 알고 있는 상태였다.

백준 - 가장 긴 증가하는 부분 수열 시리즈

---

🥲 그러나 코딩 테스트는..

코딩 테스트에 출제되는 알고리즘은 많지 않다.

BFS, DFS, 이진탐색, 브루트 포스 등… 알고리즘 자체를 익히는 것은 오래 걸리지 않는다.

그러나, 코딩테스트에서 우리의 발목을 잡는 것은 구현과 DP에서 요구하는

그래서 이 문제에 어떤 알고리즘을 쓸건데?

라는 물음에 올바른 알고리즘을 채택해야 한다는 것이다.

고등학교 수학 문제 같다는 생각이 들었다.

알고리즘을 익혔다면 그 다음 단계는 많은 문제들을 접하며 문제에 대한 알고리즘을 떠올리는 연습이 필요한 것 같다.

---

✨ LIS를 사용할 수 있는 이유

LIS는 배열에서 가장 긴 오름차순 부분 배열을 찾는데 사용한다.

그러나 문제에서 LIS를 왜 사용해야하는지 떠올리는 것이 어렵다.

문제 예시에서 A를 순서대로 확인하며 매칭되는 B값을 보자.

{8, 2, 9, 1, 4, 6, 7, 10} 인 것을 확인할 수 있다.

줄이 겹치지 않게 하려면 (1, 8), (3, 9), (4, 1) 쌍을 제거해야 한다.

이후 남는 배열은 {2, 4, 6, 7}이 된다.

즉, 이 문제에서 줄이 겹치지 않는다 -> 가장 긴 오름차순 부분 배열을 찾는다.

라는 결론이 나온다.

---

✔️ 점화식 정리

• 리스트를 유지하며, 새로운 값이 기존 리스트 마지막 값보다 크면 추가
• 아니라면, 해당 값보다 크거나 같은 최초의 위치를 찾아 해당 값을 대체

if (number[i] > list.get(list.size() - 1)) {
    list.add(number[i]);  // 증가 수열 계속 이어가기
} else {
    // number[i]가 들어갈 위치를 찾아서 교체 (수열 유지)
    for (int j = 0; j < list.size(); j++) {
        if (number[i] <= list.get(j)) {
            list.set(j, number[i]);
            break;
        }
    }
}

• 왼쪽 전봇대 위치 기준으로 오름차순 정렬을 하기 때문에, 오른쪽 값에 대해서만 비교하면 된다.

✅ 문제에서 입력 값이 커진다면?

현재 문제에서의 입력값 크기는 다음과 같다.

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다.

현재 문제에서는 전깃줄의 개수가 100 이하로 주어지므로 2중 for문을 사용해도 연산 수가 10,000번 정도이지만, 개수가 늘어난다면 시간초과가 발생할 수 있다.

이런 경우에는 **이진 탐색 (Binary Search)**를 사용하여 시간복잡도를 대폭 줄일 수 있다.

---

🖥️ 풀이 코드 (Java)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //StringTokenizer st = new StringTokenizer(br.readLine());
        int input = Integer.parseInt(br.readLine());
        int[][] inputNum = new int[input][2];
        int[] number = new int[input];
        for(int i=0;i<input;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            inputNum[i][0] = Integer.parseInt(st.nextToken());
            inputNum[i][1] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(inputNum, (a, b)->{
            if(a[0]<b[0]) return -1;
            else if(a[0]>b[0]) return 1;
            else return 0;
        });
        for(int i=0;i<input;i++) number[i] = inputNum[i][1];
        List<Integer> list = new ArrayList<>();
        list.add(number[0]);
        for(int i=1;i<input;i++){
            if(number[i] > list.get(list.size()-1)){
                list.add(number[i]);
            }
            else{
                for(int j=0;j<list.size();j++){
                    if(number[i] <= list.get(j)){
                        list.set(j, number[i]);
                        break;
                    }
                }
            }
        }
        System.out.println(input - list.size());
    }
}

---

⏰ 시간복잡도

• 이중 for문 → O(N²) (최대 100개 입력이므로 가능)
• 이분탐색 방식을 사용할 경우 O(N log N)