non-boring sequences
-
백준 3408 - Non-boring sequences문제 2024. 7. 21. 03:25
https://www.acmicpc.net/problem/3408길이 $N(\leq 200000)$의 수열이 주어졌을 때, $N$의 모든 substring이 유일한 원소를 가지면 non-boring, 아니면 boring을 출력하는 문제다. 처음에 시도한 접근법은 아래와 같다.1. 수열 전체에 유일한 원소가 없다면 그 수열은 boring이다.2. 그렇지 않다면, 해당 원소를 포함한 모든 구간은 유일한 원소를 가진다.3. 따라서 해당 원소를 기준으로 수열이 두 부분으로 나뉘어지게 되고, 각각이 non-boring이면 전체 수열도 non-boring이다.4. 이를 재귀적으로 생각한다. 그러나 위 접근법을 이용한 풀이를 내려면 수열의 임의의 구간에서 유일한 원소가 존재하는지 판별해야 하는데, 이를 빠르게 할 수..