BOJ 12950 - 팰린드롬 보행
현재 길이의 팰린드롬이고 노드와 노드에 있다고 하자.
현재 라면 짝수 길이의 팰린드롬을 찾은 것이다.
의 간선 중 로 가는 것이 있다면 홀수 길이의 팰린드롬을 찾은 것이다.
점화식은 의 간선과 의 간선 쌍 중 같은 알파벳을 가지는 것의 상태를 변경 시켜준다.
따라서 정도면 찾을 수 있다.
은 을 어디까지 진행시켜야 할지인데, 최악의 경우 한 쪽에서 간선이 하나 남았는데 그 간선은 무조건 홀수 길이의 팰린드롬에서 가장 중앙에 위치하는 경우이다.
대충 이러한 경우는 이기때문에 매우 작기 때문에 정도로 두고 돌려줘도 돌아간다.
Comments