테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 제이크와 케이크 ======

===== 풀이 =====
  * [[ps:tutorial:Necklace Splitting Problem]]의 특수한 경우
  * 최대 2번의 칼질로 원하는 분할이 가능하다. 분할 위치는 [[ps:tutorial:슬라이딩 윈도우]]로 찾으면 된다. 시간복잡도는 O(n)

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 16440. 제이크와 케이크".

- Problem link: https://www.acmicpc.net/problem/16440
- Solution link: http://www.teferi.net/ps/problems/boj/16440

Tags: [sliding window]
"""


def main():
    N = int(input())
    cake = input()

    target_s_count = N // 4
    s_count = cake[: N // 2].count('s')
    if s_count == target_s_count:
        print('1')
        print(N // 2)
        return

    for rem, add, beg in zip(cake, cake[N // 2 :], range(1, N)):
        if rem == 's':
            s_count -= 1
        if add == 's':
            s_count += 1
        if s_count == target_s_count:
            print('2')
            print(beg, beg + N // 2)
            break


if __name__ == '__main__':
    main()

</dkpr>

{{tag>BOJ ps:problems:boj:플래티넘_5}}