[BOJ 13027] Clique Problem
View as PDF
Submit solution
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text
Points:
3
Time limit:
2.0s
Memory limit:
512M
Problem types
Allowed languages
Clique Problem은 NP-complete 문제로 우리에게 잘 알려져 있다. 간단한 정의는 다음과 같다. 무향 그래프 G가 있다고 생각해 보자. 이제 그래프 G에 속한 정점들 중 부분집합인 C를 고른다. 이때 부분그래프 C에 속한 모든 정점들의 쌍은 서로 연결이 되어 있어야 한다. 즉 C는 완전 그래프라는 말과 동치다. 이때 부분그래프 C의 정점의 개수를 가장 많은 경우를 찾는것이 Clique Problem이다.</p>
위 문단을 읽었으면 우리가 무엇을 할 것인지 감이 잡힐 것이다.
N개의 중복되지 않은 점들이 X축 위에 존재한다. 이때 i번 째 점의 좌표를 xi, 무게를 wi라고 하자. 이때 N개의 점들을 가지고 그래프를 만들 수 있다. 서로 다른 두 점 i, j가 wi + wj ≤ |xi - xj|을 만족 한다면 연결되어 있다고 생각한다.
이렇게 만들어진 그래프에서 가장 Clique Problem을 푸는것이 우리의 목표다.
입력 형식
첫 번째 줄에 n (1 ≤ n ≤ 200,000) 이 주어진다. 이는 X축 위에 존재하는 점의 개수이다.</p>
두 번째 줄부터 n개의 줄에 걸쳐 두 개의 수 xi, wi(1 ≤ xi, wi ≤ 109) 이 주어진다.
모든 xi는 다르다는 것이 보장된다.
출력 형식
첫 번째 줄에 입력받은 점들로 만든 그래프의 부분집합 중 완전그래프가 되는 가장 큰 부분집합의 크기를 출력한다.
예제 입력
4
2 2
3 1
6 2
1 1
예제 출력
3
Comments