[백준] Baekjoon Online Judge
문제
N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다.
- P1 IOI
- P2 IOIOI
- P3 IOIOIOI
- PN IOIOI...OI (O가 N개)
I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.
출력
S에 PN이 몇 군데 포함되어 있는지 출력한다.
제한
- 1 ≤ N ≤ 1,000,000
- 2N+1 ≤ M ≤ 1,000,000
- S는 I와 O로만 이루어져 있다.
풀이
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int N, M;
string S;
cin >> N >> M >> S;
char c[2] = { 'I', 'O' };
int need = 1 + 2 * N;
int result = 0, cnt = 0;
bool now = false;
for (int i = 0; i < M + 1; i++) {
if (S[i] == c[now]) {
cnt++;
now = !now;
}
else {
if (cnt >= need) result += (cnt - need) / 2 + 1;
if (S[i] == 'I') i--;
cnt = 0;
now = false;
}
}
cout << result << '\n';
return 0;
}
입력 받은 문자열 S를 처음부터 끝까지 for문으로 검사하는 방식으로 문제를 풀었다. c[2]와 now로 I와 O가 교대로 나오는지 확인하도록 했다. 이때 찾은 문자열에서 Pn의 개수는 (문자열의 길이 - Pn의 길이) / 2 + 1이
'백준 > C++' 카테고리의 다른 글
[Baekjoon/C++] 20529번 - 가장 가까운 세 사람의 심리적 거리 (0) | 2023.11.07 |
---|---|
[Baekjoon/C++] 7576번 - 토마토 (0) | 2023.11.05 |
[Baekjoon/C++] 2667번 - 단지번호붙이기 (0) | 2023.11.02 |
[Baekjoon/C++] 13305번 - 주유소 (1) | 2023.11.02 |
[Baekjoon/C++] 11004번 - K번째 수 (1) | 2023.11.02 |