[백준 BOJ] 23245. Similarity (2021 ICPC 인터넷 예선 H번)
18 Jul 2022난이도
Platinum IV
문제 풀이
작년 인예때는 세그 트리 문제인것만 직감하고 못풀었는데, 이제 풀 실력이 만들어졌다. 새벽에 야무지게 풀고 신나서 풀이 쓰는 중이다.. 하여튼 대충 정렬 + 약간의 DP(?) + 세그먼트 트리로 풀 수 있는 문제이다.
문제에서 구해야하는 것은 두 수열이 주어졌을 때, 오름차순을 만들 수 있는 인덱스 쌍 \(\scriptsize (i, j, k)\)의 개수를 찾는 것이다. 일단, \(\scriptsize i, j, k\) 모두가 변하면 어질어질하니 \(\scriptsize p, q\)를 묶어서 정렬해주자.
std::pair를 이용해서 정렬해주면, first에 담긴 쪽은 오름차순이 된다. 이제 second를 보고 순서쌍 개수를 세어주면 되는데, 내가 생각한 방법은 다음과 같다. 먼저, 배열 하나를 정의해보자.
\(cnt(i) :=\) “i로 끝나는 2자리 증가수열의 개수”
이렇게 \(\scriptsize cnt\)를 정의하면, 2개짜리 증가 순서쌍은 찾을 수 있다.
\[cnt(i) = \sum_{j < i \land q[j] < q[i]} 1\]
naive하게 계산하면 \(\scriptsize O(n^{2})\)이지만, 세그먼트 트리로 최적화해줄 수 있으니 \(\scriptsize O(nlogn)\) 만에 배열을 채울 수 있다.
segment_tree tree(MAX + 1);
vector<ll> cnt(n + 1);
for(int i = 1; i <= n; ++i) {
cnt[i] = tree.query(0, MAX, 1, 0, X[i].second - 1);
tree.update(0, MAX, 1, X[i].second, 1);
}
cnt 배열은 \(\scriptsize i < j\) 인 쌍의 개수를 센거니까 이제 \(\scriptsize i < j < k\) 개수를 세어보자. \(\scriptsize cnt\)를 채우는 것과 비슷하게 개수를 세줄 수 있다. 요것도 역시 세그먼트 트리로 샤샥 해주면 된다.
\[\sum_{j < i \land q[j] < q[i]} cnt[j]\]
ll ans = 0;
segment_tree tree_cnt(MAX + 1);
for(int i = 1; i <= n; ++i) {
ans += tree_cnt.query(0, MAX, 1, 0, X[i].second - 1);
tree_cnt.update(0, MAX, 1, X[i].second, cnt[i]);
}
현재보고 있는 원소보다 작은 원소들의 \(\scriptsize cnt\)값을 다 더하면 그게 우리가 찾는 값이니까 반복문을 돌면서 답에 더해주면 된다. 이렇게 하면 답이 잘 안나온다. 왜냐면, 중복된 원소에 대해서 값을 잘못 세기 때문이다. \(\scriptsize p\)값이 같을 때에는 \(\scriptsize q\)값이 큰 걸 먼저 앞에 둬야지 값을 제대로 셀 수 있다. 정렬을 똑바로 하고 답 출력해주면 AC!
1-based로 코드를 썼는데, 그러다가 sort 시작을 begin + 1이 아닌 begin으로 해버려서 맞왜틀 좀 했었다.. 혹시 너무 맞는거 같은데 틀린다면 이게 원인일 수 있다.