ps:problems:boj:16440
제이크와 케이크
| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 16440 |
| 문제명 | 제이크와 케이크 |
| 레벨 | 플래티넘 5 |
| 분류 |
슬라이딩 윈도우 |
| 시간복잡도 | O(n) |
| 인풋사이즈 | n<=200,000 |
| 사용한 언어 | Python 3.11 |
| 제출기록 | 31120KB / 36ms |
| 최고기록 | 36ms |
| 해결날짜 | 2024/12/01 |
풀이
- Necklace splitting problem의 특수한 경우
- 최대 2번의 칼질로 원하는 분할이 가능하다. 분할 위치는 슬라이딩 윈도우로 찾으면 된다. 시간복잡도는 O(n)
코드
"""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()
ps/problems/boj/16440.txt · 마지막으로 수정됨: 2024/12/01 04:19 저자 teferi

토론