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
토론