백준 2565: 전깃줄

Gold V 난이도 문제를 C++로 풀이한 내용입니다. 서로 교차하지 않는 전깃줄의 최대 개수를 구하는 문제입니다.

문제 소개

• 문제 번호: 2565
• 문제명: 전깃줄
• 난이도 (티어): Gold V
• 사용 언어: C++
• 실행 시간: 0 ms
• 메모리: 2024 KB
• 문제 요약:
  건물 A와 B 사이에 N개의 전깃줄이 연결되어 있습니다. 각 전깃줄은 A의 한 지점과 B의 한 지점을 연결합니다. 두 전깃줄이 서로 교차하지 않도록 하기 위해 제거해야 할 전깃줄의 최소 개수를 구해야 합니다.

접근 방법

• 문제 이해:
  문제는 두 건물을 잇는 전깃줄들이 서로 꼬이지 않도록 하는 것입니다. 두 전깃줄이 교차한다는 것은 한 전깃줄의 시작점보다 다른 전깃줄의 시작점이 앞서지만, 끝점은 뒤서거나, 그 반대인 경우입니다. 즉, A 지점에서의 순서와 B 지점에서의 순서가 서로 바뀌는 경우에 교차가 발생합니다.

• 알고리즘/자료구조:
  이 문제는 최장 증가 부분수열(LIS) 알고리즘을 활용하여 해결할 수 있습니다.

  1. A 지점을 기준으로 전깃줄을 정렬합니다.
  2. 정렬된 A 지점의 순서에 따라 B 지점의 연결된 값들을 나열합니다.
  3. 나열된 B 지점 값들의 LIS를 찾습니다. LIS는 전깃줄이 교차하지 않는 최대 개수를 의미합니다.
  4. 전체 전깃줄 개수에서 LIS 길이를 빼면 제거해야 할 최소 전깃줄 개수가 됩니다.

• 선택 이유:
  A 지점을 기준으로 전깃줄을 정렬하면, B 지점의 값들이 증가하는 순서로만 나열했을 때 전깃줄이 교차하지 않습니다. 따라서, B 지점 값들의 수열에서 최장 증가 부분수열을 찾는 것은 교차하지 않는 전깃줄의 최대 개수를 찾는 것과 같습니다.

풀이 과정

1. 입력 처리:

   • N개의 전깃줄에 대한 A 지점과 B 지점의 연결 정보를 입력받습니다.
   • 각 전깃줄을 pair<int, int> 형태로 저장하여 A 지점과 B 지점의 연결 정보를 묶습니다.

2. A 지점 기준 정렬:

   • 입력받은 전깃줄 정보를 A 지점의 숫자가 작은 순서대로 정렬합니다. std::sort 함수를 사용합니다.

3. B 지점 수열 추출:

   • A 지점 기준으로 정렬된 전깃줄 정보를 바탕으로, B 지점의 연결된 값들을 순서대로 b_seq라는 벡터에 저장합니다. 이 b_seq 벡터는 LIS를 찾기 위한 대상이 됩니다.

4. LIS 계산 (DP):

   • dp 벡터를 사용하여 LIS의 길이를 계산합니다. dp[i]는 i번째 B 지점 값(b_seq[i])까지 고려했을 때 만들 수 있는 LIS의 길이입니다.
   • dp 벡터를 모두 1로 초기화합니다. (각 원소 하나만으로도 길이가 1인 LIS를 만들 수 있습니다.)
   • 두 개의 중첩 반복문을 사용하여 dp 값을 계산합니다.
     • 바깥쪽 루프(i): 현재 LIS 길이를 계산할 b_seq[i]를 선택합니다.
     • 안쪽 루프(j): i보다 앞에 있는 b_seq[j]를 확인합니다.
     • 핵심 아이디어: 만약 b_seq[j] < b_seq[i]이면, b_seq[i]는 b_seq[j]를 포함하는 LIS에 연결될 수 있습니다. 이때, dp[i]는 dp[j] + 1과 기존 dp[i] 값 중 더 큰 값으로 갱신됩니다. 이는 b_seq[i]를 마지막으로 하는 LIS의 최대 길이를 유지하기 위함입니다.

5. LIS 길이 최댓값 찾기:

   • dp 벡터에서 가장 큰 값을 찾습니다. 이 값이 교차하지 않는 전깃줄의 최대 개수, 즉 LIS의 길이가 됩니다. std::max_element 함수를 사용합니다.

6. 최소 제거 개수 계산:

   • 전체 전깃줄 개수(n)에서 LIS 길이(LIS_length)를 뺍니다. 이 값이 제거해야 할 최소 전깃줄의 개수입니다.

7. 결과 출력:

   • 계산된 최소 제거 개수를 출력합니다.

코드 설명

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*
  2565번 전깃줄
  
  [문제 분석]
  교차 정의: (a' > a AND b' < b) OR (a' < a AND b' > b)
  
  [논리적 유도]
  교차하지 않는 조건 = 교차 조건의 부정
  NOT[(a' > a AND b' < b) OR (a' < a AND b' > b)]
  = (a' <= a OR b' >= b) AND (a' >= a OR b' <= b)
  
  [분배법칙 적용]
  (X OR Y) AND (Z OR W) = (X AND Z) OR (X AND W) OR (Y AND Z) OR (Y AND W)
  X=a'<=a, Y=b'>=b, Z=a'>=a, W=b'<=b
  
  = (a' = a) OR (a' <= a AND b' <= b) OR (a' >= a AND b' >= b) OR (b' = b)
  
  [조건 적용]
  같은 위치에 2개 이상 불가 → a' ≠ a, b' ≠ b
  = (a' < a AND b' < b) OR (a' > a AND b' > b)
  
  [결론]
  교차하지 않으려면: 둘 다 앞이거나 OR 둘 다 뒤여야 함
  A를 정렬하면 이미 증가 순서 → B도 증가 순서여야 함
  = B의 LIS(최장 증가 부분수열) 찾기
  
  [답]
  제거할 줄 개수 = 전체 줄 개수 - LIS 길이
*/

int main() {
    // 표준 입출력 성능 향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n; // 전깃줄의 개수
    cin >> n;
    
    // A 위치 순서로 정렬하기 위해 페어 사용
    // wires[i].first: A 지점, wires[i].second: B 지점
    vector<pair<int, int>> wires(n);
    for (int i = 0; i < n; i++) {
        cin >> wires[i].first >> wires[i].second;
    }
    
    // A 위치 순서로 정렬 (first 값 기준 오름차순)
    sort(wires.begin(), wires.end());
    
    // B 수열 추출 (A 기준으로 정렬된 상태에서의 B 값들)
    vector<int> b_seq(n);
    for (int i = 0; i < n; i++) {
        b_seq[i] = wires[i].second; // second가 A 정렬 상태에서의 B 값들
    }
    
    // DP: dp[i] = i번째 원소까지 고려했을 때 LIS 길이
    vector<int> dp(n, 1); // 각 원소 자체로 길이가 1인 LIS를 만듦
    
    // LIS 계산
    for (int i = 1; i < n; i++) { // i = 0일 때는 원소 하나로 LIS이므로 dp[i] = 1이니 스킵
        for (int j = 0; j < i; j++) { // i의 앞에 있는 원소들을 순회하며(A 정렬 순서) 체크하며
            if (b_seq[j] < b_seq[i]) { // b가 증가했으면 (앞의 B값이 더 작으면)
                // 현재 LIS 길이를 더 확장할 수 있음
                dp[i] = max(dp[i], dp[j] + 1); // LIS에 통합 (이전 LIS 길이에 1 더함)
            }
        }
    }
    
    // LIS의 최댓값 찾기
    // LIS_length는 교차하지 않는 전깃줄의 최대 개수
    int LIS_length = *max_element(dp.begin(), dp.end());
    
    // 제거할 줄의 최소 개수 = 전체 줄 개수 - 교차하지 않는 최대 개수
    int answer = n - LIS_length;
    
    cout << answer;
    return 0;
}

복잡도 분석

• 시간 복잡도:

  • 전깃줄을 정렬하는 데 $O(N\log N)$ 시간이 소요됩니다.
  • LIS를 계산하기 위해 두 개의 중첩 반복문이 사용되는데, 이는 $O(N^2)$ 시간이 소요됩니다.
  • 따라서, 전체 시간 복잡도는 $O(N^2)$입니다. (LIS 계산이 가장 큰 영향을 미칩니다.)

• 공간 복잡도:

  • wires 벡터에 $O(N)$ 공간이 사용됩니다.
  • b_seq 벡터에 $O(N)$ 공간이 사용됩니다.
  • dp 벡터에 $O(N)$ 공간이 사용됩니다.
  • 따라서, 전체 공간 복잡도는 $O(N)$입니다.

배운 점

• 두 선분이 교차하지 않는 조건을 어떻게 LIS 문제로 변환할 수 있는지 이해했습니다.
• A 지점을 기준으로 정렬하는 것이 B 지점에서의 LIS를 찾는 핵심 아이디어임을 알게 되었습니다.
• DP를 이용한 LIS 알고리즘의 구현 방법을 익혔습니다.
• std::pair와 std::sort를 활용하여 데이터를 효과적으로 관리하는 방법을 배웠습니다.
• ios_base::sync_with_stdio(false)와 cin.tie(NULL)을 사용하여 C++ 표준 입출력 속도를 개선하는 방법을 실습했습니다.