Dot Algo∙ DS/PS
2022. 1. 31.
[BOJ] 백준 1615번 교차개수세기 (Java)
#1615 교차개수세기 난이도 : 플레 5 유형 : 세그먼트 트리 / 펜윅 트리 1615번: 교차개수세기 첫 줄에 N과 간선의 개수 M이 주어진다. 그 다음 줄부터 M+1번째 줄까지 두 개의 수(i, j)가 주어지는데 이는 왼쪽 그룹의 i번 정점과 오른쪽 그룹의 j번 정점을 연결하는 간선이 있다는 의미이다. www.acmicpc.net ▸ 문제 각각 N(1 ≤ N ≤ 2,000)개의 쌍으로 이루어진 2N개의 정점과 M(1 ≤ M ≤ N×(N-1)/2)개의 간선으로 구성된 이분그래프가 주어질 때 서로 교차하는 총 개수를 구하는 것이다. 교차 조건 : 한 독립 집합 A와 다른 독립 집합 B가 연결된 두 개의 간선을 (A1, B1), (A2, B2)라 한다면 A1 B2 또는 A1 > A2,..
![[BOJ] 백준 1615번 교차개수세기 (Java)](http://i1.daumcdn.net/thumb/C450x300/?fname=https://blog.kakaocdn.net/dn/nhnJr/btrscO5MHpx/QY6iUmS8QqocsNPKByeYr0/img.png)