[ICPC] 백준 23245 - Similarity

https://www.acmicpc.net/problem/23245

 

대회 당시 내가 푼 문제임에도 불구하고 귀찮다는 이유로 안 쓰고 있었는데 다른 글들을 둘러보니 나와는 다른 방향으로 푼 거 같아 작성하고자 한다.

 

사실 여기서 적을 것은 별로 없다. 주어진 수열 쌍을 적절히 오름차순으로 정렬하고 좌표 압축을 수행하면 아래 문제와 조건이 동일해진다.

 

https://www.acmicpc.net/problem/17409

17409번: 증가 수열의 개수

 

그러면 위 문제에서 k가 3인 버전으로 생각하고 세그먼트 트리로 LIS 카운팅 DP를 수행하면 된다. 자세한 풀이는 여기를 참고하라.

 

그런데 다른 사람들은 여우가 정보섬에 올라온 이유의 다른 버전으로 간주하고 풀었다는 것 같다. 구현의 편의성은 LIS 카운팅을 하는 게 더 간편한 것 같다.

제출 기록(대회)

이 문제는 H번으로 출제되었다.

여담

대회 당시 이 문제를 풀게 된 데에는 기막힌 사연이 있는데 본인이 대회 종료 15분 전까지 붙잡고 있다가 LIS 카운팅을 하는 문제라는 것을 발견한 것이다. 심지어 17409는 대회가 시작하기 얼마 남지 않은 시점에 공부했던 것이다.

 

거기에 얹어서 아직 부족한 실력에 팀 노트에 적을 게 없자 대충 채우는 용도로 LIS 카운팅을 하는 코드를 넣어뒀었는데 그걸 또 운 좋게도 쓸 수 있는 문제가 등장한 것이었다.

 

이렇게 학교 2등 자격으로 본선 티켓을 따냈지만 모종의 사고가 발생하여 갈 수 없게 된다.

 

그리고 이는 UCPC 2022 팀명을 "한정택 <== ICPC 2021 본선 탈주범"으로 짓는 결정적인 사건이 된다.

 

기회가 된다면 블로그에 팀 연습 결산을 할 때 간략하게 언급하도록 하겠다.