https://www.acmicpc.net/problem/5525
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이 몇
www.acmicpc.net
문제 정리
I와 O가 반복된 배열이 주어짐.
1: IOI
2: IOIOI
3: IOIOIOI
이런 식으로 반복되는 수열의 길이 N이 주어짐.
배열안에 N으로 이루어진 IOI가 얼마나 있는지 구함.
예를 들어 N이 4라는 것은 IOIOIOIOI 이 부분이 배열에 얼마나 있냐는 것이다.
주어진 배열이 OOOIOIOIOIOIOIOOO라고 하면 답은 2개가 된다.
이유는 OOOIOIOIOIOIOIOOO 1개
그 다음 OOOIOIOIOIOIOIOOO 2개 이렇게 해서 2개이다.
문제 해결 방법
저는 bool 변수를 통해서 배열에서 탐색을 하는데 전전인덱스, 전인덱스, 현인덱스 이렇게 비교를 해서
IOI이면 카운트를 세주었습니다.
bool변수가 true이면 I이고 false면 O로 했습니다.
IOI가 얼마나 연속으로 이어지는지 센 후 길이 N을 빼준 다음 +1을 하면 그것이 연속된 IOI에서 나올 수 있는 길이 N의 IOI배열이 되겠습니다.
주의해야할 것은 IOI가 한번 나오면 그 다음 연속 IOI는 IOIIOI가 아니라 IOIOI이기 때문에 카운트가 한번된 상황이라면
IOI이후 OI라면 연속된 배열이라고 판단해주어야합니다. 그 후 연속된 배열을 세다가 연속하지 않는다면 카운트를 0으로 만들어주고 연속된 배열안에서 몇개의 N개의 연속된 IOI를 만들 수 있는지 더해준후 다시 반복해주면됩니다.
전체 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
#include <iostream>
#include <string>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
string s;
cin >> s;
bool bbe; // 전전것이 무엇이였는지
bool be; // 전것이 무엇이였는지
if(s[0] == 'I')
bbe = true;
else
bbe = false;
if(s[1] == 'I')
be = true;
else
be = false;
bool cur; // 현재 것
int cnt = 0;
int result = 0;
for (int i = 2; i < m;i++){
if(s[i] == 'I') // 현재 인덱스
cur = true;
else
cur = false;
if(bbe && !be && cur){ // IOI 일 때
cnt++;
}else if(cnt > 0 && !bbe && be && !cur){
//IOI가 앞에 있고 그 뒤에 IOIOI이런 상황이라면 연속된 것으로 판단.
true;
}else{ // IOI연속이 깨졌을 경우
if(cnt - n > -1)
result += cnt - n + 1; // 정답에 저장
cnt = 0; // 카운트 초기화
}
bbe = be; // 전전것에 전것을 옮겨주고
be = cur; // 전것에 현재것을 옮겨줌
}
if(cnt - n > -1){ // 마지막으로 연속된 IOI가 있을 경우를 처리
result += cnt - n + 1;
}
cout << result << '\n';
return 0;
}
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
백준 16236 아기 상어 c++ [컴공과고씨] (0) | 2022.09.03 |
---|---|
백준 17219 비밀번호 찾기 c++ [컴공과고씨] (0) | 2022.09.03 |
백준 6064 카잉 달력 c++ [컴공과고씨] (0) | 2022.08.16 |
백준 5430 AC c++ [컴공과고씨] (0) | 2022.08.14 |
백준 14500 테트로미노 C++ [컴공과고씨] (0) | 2022.08.14 |