https://www.acmicpc.net/problem/14594
14594번: 동방 프로젝트 (Small)
첫 번째 행동으로 1번과 2번 방이 합쳐져 (1, 2), (3), (4), (5) 상태가 된다. 이후 두 번째 행동으로 2, 3, 4번 방이 합쳐져 (1, 2, 3, 4), (5)의 상태가 된다. 따라서 남아있는 동방의 수는 2가 된다.
www.acmicpc.net
유니온 파인드 문제다. 문제는 같지만 입력 범위가 넓은 14595 문제를 풀다가 시간 초과하여 범위가 좁은 해당 문제부터 풀어보았다.
풀이
들어온 입력에 맞게 범위 단위로 유니온을 해준뒤 루트의 개수를 세면 된다. x < y 라는 조건이 있으니, x의 루트만 찾아낸 후 x+1 ~ y 범위까지 전부 x의 루트로 변경하면 된다.
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [2143] 두 배열의 합 (0) | 2022.12.20 |
|---|---|
| [2610] 회의준비 (0) | 2022.12.19 |
| [16168] 퍼레이드 (0) | 2022.12.16 |
| [13905] 세부 (0) | 2022.12.14 |
| [16724] 피리 부는 사나이 (0) | 2022.12.13 |