치춘짱베리굿나이스
[백준] 5525 본문
IOIOI
문제
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이 몇 군데 포함되어 있는지 출력한다.
풀이
#include <iostream>
#include <string>
int main(void) {
int n, m, cnt = 0, nOfOIs;
std::string str;
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin >> n >> m;
std::cin >> str;
for (int i = 0; i < m; i++) {
nOfOIs = 0;
if (str[i] == 'O')
continue;
while (str[i + 1] == 'O' && str[i + 2] == 'I') {
nOfOIs++;
i += 2;
if (nOfOIs == n) {
nOfOIs--;
cnt++;
}
}
}
std::cout << cnt << "\n";
}
반성회
I
를 찾으면 그 뒤에 따라오는OI
의 개수를 센다nOfOIs
가OI
의 개수- 인덱스
i
는OI
마다 2씩 올라간다
- 만약
OI
의 개수nOfOIs
가n
개를 달성할 경우cnt
를 1 올린다 (원하는IOIOI…
1개 발견)nOfOIs
를 1 깎는다IOIOIOI…
에서 첫 번째IOIOI…
를 찾았다면 앞의IOIOI…
에서OI
개수를 1개 줄이는 이유는 그 다음OI
부터 다음IOIOI...
를 찾기 시작하기 때문- 이 원리로 for 문을 한 번만 돌아서
IOIOI…
를 찾을 수 있다
'C C++ > 알고리즘풀이' 카테고리의 다른 글
[백준] 19947 (0) | 2023.09.26 |
---|---|
[백준] 1916 (0) | 2023.09.24 |
[백준] 12871 (0) | 2023.09.21 |
[백준] 5648 (0) | 2023.09.20 |
[백준] 3060 (0) | 2023.09.18 |
Comments