- 문제 링크
백준 2565번 - 전깃줄
해결 전략
본 문제를 처음 접했을 때, 아래와 같은 두 가지 정도의 풀이 방법이 떠올랐다.
1. a를 기준으로 오름차순 정렬 후, b를 기준으로 가장 긴 (연속하는) 증가부분수열을 구한다. n에서 그 길이를 빼면 그것이 곧 정답이다.
2. 전깃줄들을 입력받은 후, cross되는 전깃줄의 개수를 각각 기록한 후, 그 값을 기준으로 내림차순 정렬 후, 가장 cross가 많이 된 전깃줄부터 차례로 제거하고, 그 정보를 업데이트해나가는 Greedy Algorithm을 구성해, 모든 전깃줄의 cross가 0이 될 때까지 알고리즘을 수행하면, 그 순회 횟수가 곧 정답이다.
최초로 1번 아이디어를 시도한 후, 옳지 않다 판단 후 2번 그리디 알고리즘 풀이로 2시간 가량을 소모했다. 왠만한 입력 상황을 다 커버함에도 왜 '틀렸습니다'가 나오는지 의아해 결국 백준 사이트 내의 몇 가지 질문들을 검색한 후 본 문제가 DP 문제임을 깨달았다.
그 순간, 폐기했던 1번 아이디어가 곧 정답으로 이어짐을 알 수 있었다. 단, 한 가지 조정이 필요했다.
증가부분수열이 꼭 연속할 필요가 있는가? 어차피 사이사이의 cross 전깃줄만을 제거하면 되지 않는가.
그렇다, 본 문제는 가장 대표적이고 기본적인 Dynamic Programming 예제인 LIS의 활용 문제였던 것이다. 그것도 매우 간단한 형태의. 이를 깨달은 후 어렵지 않게 문제를 해결할 수 있었다.
대표 예시
8
1 8
3 9
2 2
4 1
6 4
10 10
9 7
7 6
를 보면, 이를 a를 기준으로 정렬하자.
1 8
2 2
3 9
4 1
6 4
7 6
9 7
10 10
여기서 b를 배열로 보면
8 2 9 1 4 6 7 10이고, 이 배열에서 가장 긴 증가 부분 수열의 길이 k를 구하면, n-k가 곧 제거해야할 최소 전깃줄 개수가 된다. 당연한 것이, 순서에 어긋나는 요소들만 빼버리면 되기 때문이다.
추가적인 설명은 불필요할 것이다. 아래는 정답 코드이다.
#include <iostream>
#include <algorithm>
// BOJ - 2565 Electric Line
using namespace std;
typedef struct { int a; int b; } Line;
Line line[100];
int LIS[100]; // LIS[i] : line[i].b로 끝나는 가장 긴 증가부분수열
bool pred(Line x, Line y) { if (x.a < y.a) return true; return false; }
int solve(int n) {
int MAXIMUM = 1;
sort(line, line + n, pred);
for (int i = 0; i < n; i++) { LIS[i] = 1; }
for (int i = 1; i < n; i++) {
int MAX = 0;
for (int j = 0; j < i; j++)
if (LIS[j] > MAX && line[j].b < line[i].b) MAX = LIS[j];
LIS[i] = MAX + 1;
}
for (int i = 0; i < n; i++)
if (MAXIMUM < LIS[i]) MAXIMUM = LIS[i];
return MAXIMUM;
}
int main(void) {
int n;
cin >> n;
for (int i = 0; i < n; i++) { cin >> line[i].a >> line[i].b; }
cout << n - solve(n);
return 0;
}이어서 아래는 폐기된 Greedy Algorithm 풀이 코드이다. 당연히 틀린 풀이이다. 이 풀이로 해결을 원한다면, 아래의 코드에 추가적으로 cross된 전깃줄들에 대한 정보를 실시간으로 고려해야하는데, 그 과정은 매우매우 복잡할 것이다. 위의 DP식 풀이가 훨씬 현명하다.
#include <iostream>
#include <algorithm>
// BOJ - 2565 Electric Line
using namespace std;
typedef struct { int a; int b; int cross = 0; int index; bool removed = false; } Line;
Line line[100];
bool pred(Line a, Line b) { if (a.cross > b.cross) return true; return false; }
int solve(int n) {
int cnt, lineCnt = 0;
bool noflag = true;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (line[j].a < line[i].a && line[j].b > line[i].b) line[i].cross++;
if (line[j].a > line[i].a && line[j].b < line[i].b) line[i].cross++;
}
for (int i = 0; i < n; i++) { if (line[i].cross > 0) noflag = false; }
if (noflag) return 0;
for (int i = 0; i < n; i++) {
sort(line, line + n, pred);
line[0].cross = 0; line[0].removed = true;
for (int j = 0; j < n; j++) {
if (line[line[j].index].removed) continue;
if (line[line[j].index].a < line[0].a && line[line[j].index].b > line[0].b)
line[line[j].index].cross--;
if (line[line[j].index].a > line[0].a && line[line[j].index].b < line[0].b)
line[line[j].index].cross--;
}
lineCnt++;
noflag = true;
for (int i = 0; i < n; i++) { if (line[i].cross > 0) noflag = false; }
if (noflag) break;
}
return lineCnt;
}
int main(void) {
int n;
cin >> n;
for (int i = 0; i < n; i++) { cin >> line[i].a >> line[i].b; line[i].index = i; }
cout << solve(n);
return 0;
}