본문 바로가기

알고리즘/백준 문제풀이

[BOJ 2568] 전깃줄 - 2

반응형

문제 출처 : https://www.acmicpc.net/problem/2568

 

2568번: 전깃줄 - 2

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500,000 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다. 

www.acmicpc.net

LIS (Longest Increasing Subsequence, 최장 증가 부분 수열) 유형의 문제이다. 

전깃줄이 순서없이 입력되기 때문에 A 또는 B를 기준으로 정렬을 해주어야 한다. 

A를 기준으로 정렬한다면, 정렬된 후의 B 수열을 가지고 LIS 알고리즘을 이용한다. 

 

LIS 알고리즘 (https://wogud6792.tistory.com/33)

 

LIS (Longest Increasing Subsequence) - 최장 증가 부분 수열

주어진 수열에서 <최장 증가 부분 수열 (Longest Increasing Subsequence)> 을 구하는 문제 유형을 알아보자. 사실 이 유형은 DP(Dynamic Programming) 문제로 자주 나오는 유형이며, O(N^2)의 시간복잡도를 갖는..

wogud6792.tistory.com

 

 

이 때, 출력하고자 하는 것이 LIS의 길이뿐만 아니라 구체적인 LIS도 알아야 하고,

A에 연결된 번호를 출력해야 하므로 B를 기준으로 정렬했다면 없어진 전깃줄을 찾아 A와 연결해야 한다. 

(B를 기준으로 정렬했다면 더 간단했을거 같기도 하다...)

 

소스 코드)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//BOJ 2568 전깃줄 - 2
#include<iostream>
#include<algorithm>
#include<stack>
#include<cmath>
#include<functional>
#include<string>
 
using namespace std;
 
struct line {
    int A;
    int B;
};
bool compare(line a, line b) {
    return a.A < b.A;
}
 
line L[100001];
int A[500001];
int ans[100001];
int index[100001];
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N; 
    int idx = 0;
    int a, b;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> a >> b;
        L[i].A = a;
        L[i].B = b;
    }
    sort(L+1, L + N+1, compare);
 
    for (int i = 1; i <= N; i++) {
        if (idx == 0)
        {
            A[idx++= L[i].B;
            index[1= 1;
        }
        else {
            if (A[idx - 1< L[i].B)
            {
                index[i] = idx+1;
                A[idx++= L[i].B;
            }
            else {
                index[i] = lower_bound(A, A + idx, L[i].B) - A+1;
                A[lower_bound(A, A + idx, L[i].B) - A] = L[i].B;
            }
        }
    }
 
    cout << N-idx << '\n';
    int t = 0;
 
    for (int i = N; i >= 1; i--) {
        if (idx == index[i]) idx--;
        else {
            ans[t++= L[i].A;
        }
    }
    sort(ans, ans + t);
    for (int i = 0; i < t; i++cout << ans[i] << '\n';
}
 

 

반응형

'알고리즘 > 백준 문제풀이' 카테고리의 다른 글

[BOJ 12920] 평범한 배낭 2  (3) 2020.07.07
[BOJ 2517] 달리기  (0) 2020.05.01
[BOJ 11066] 파일 합치기  (0) 2019.07.22
[BOJ 1725] 히스토그램  (0) 2019.03.30
[BOJ 1992] 쿼드트리  (0) 2019.03.30