BOJ 28000 Tourism
#소개2022/2023 JOISC 3-3 기출 문제로, 난이도는 solved.ac 기준 Diamond II입니다.제 풀이가 정해와 달라 풀이를 작성해보려고 합니다. #문제 요약- $N$개의 정점을 가진 트리 형태의 섬들과, $M$개의 관광 명소가 각각 섬 $C_1, C_2, ... , C_M$에 위치해 있다. 다음과 같은 $Q$개의 쿼리를 처리해야 한다.- $L\text{ }R$ : $C_L, C_{L+1}, ... , C_R$까지의 섬을 모두 방문하기 위해 지나야 하는 섬들의 최소 개수를 출력한다.- $1 \le N, M, Q \le 100,000$ #사용한 알고리즘- 세그먼트 트리- 최소 공통 조상- 오프라인 쿼리- 오일러 경로 테크닉- 희소 배열 #풀이*다음과 같이 정의합니다.$C_1, C_2, ...
2025. 5. 10.
