백준 5525 - IOIOI(C++)

문제 링크입니다. https://www.acmicpc.net/problem/5525

5525번: IOIOI

문자열을 이용한 문제였습니다. 

문제 조건

출력 예시

"IOI" 를 확인하는 과정에서 다중 for문을 사용한다면 시간초과가 생기기에 다른 접근이 필요한 문제였습니다.

저같은 경우에는 IOI가 연속적으로 몇번 나오는지를 확인하는 방법으로 풀었습니다.

 

예제입력을 통해서 확인해보겠습니다.

OOIOIOIOIIOII 해당 문자열이 주어졌을때, 연속된 "IOI"를 가지는 문자열은 OOIOIOIOIIOII 가 됩니다.

각각 3개, 1개로 이루어져있습니다. 이때, N이 1이라면, 3 + 1이 되며, N이 2라면, 3 - 2 + 1이 되어 2가 됩니다.

 

N의 값에 따라 연속된 갯수를 찾아보겠습니다.IOIOIOIOIOI 해당 문자열이 주어졌을때, IOI가 연속되는 값은 5가 됩니다.

N이 2라면, 5 - 2 + 1인 4가 되며,

N이 3이면, 5 - 3 + 1인 3이 되며,

N이 4라면, 5 - 4 + 1인 2가 됩니다.

따라서 식을 세워보자면, X - N + 1이 됩니다. (X는 연속된 IOI의 값)

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>

using namespace std;

int N, M;
vector<int> v;
string IOI;
int continue_;

int Find() {
	int cnt = 0;
	int ans = 0;
	while (1) {
		if (cnt == M) break;
		if (IOI[cnt] == 'I' && cnt + 2 < M) {
			if (IOI[cnt + 1] == 'O' && IOI[cnt + 2] == 'I') {
				cnt += 2;
				continue_++;
			}
			else {
				if(continue_ != 0)v.push_back(continue_);
				cnt++;
				continue_ = 0;
			}
		}
		else {
			if(continue_ != 0)v.push_back(continue_);
			cnt++;
			continue_ = 0;
		}
	}
	for (int i = 0; i < v.size(); i++) {
		if (v[i] >= N) {
			ans += v[i] - N + 1;
		}
	}
	return ans;
}

void solve() {
	int ans = Find();
	cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	cin >> M;
	cin >> IOI;
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!