분할 정복. [5904]

[1. 문제 설명]

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

---

[2. 풀이 접근]

생성 되는 문자열은 Left / Middle / Right 로 구성 되고 있으며,

여기서 Left 와 Right 는 서로 같다.

 

최소 어느 정도의 k 일 때 해당 문자열이 찾고하는 위치를 포함하게 된다.

 

여기서, Left 와 Middle 의 문자열 각각의 길이를 알 수 있기 때문에

 

찾고자 하는 문자열이 Left 와 Middle 의 속하는지 확인하고,

Left 에 속하면 재귀 호출을 반복하고,

Middle 에 속하면 M 인지 O 인지 바로 알 수 있다.

 

마지막으로 Right 에 속하는 경우는 Left 에 속하는 것과 같다고 볼 수 있으므로,

찾고자 하는 문자의 위치를 Left 와 대칭되는 위치로 변경하여 재귀 호출하도록 한다.

---

[3. 코드]