[백준] 5525번 IOIOI - C++

IOIOI

P(N) : P(1) = "IOI", P(2) = "IOIOI", P(3) = "IOIOIOI",... 일 때 주어진 문자열 S에 P(N)이 몇 군데 포함되어 있는지 출력하는 문제입니다.

입력

첫째 줄에 N, 둘째 줄에 S의 길이 M, 셋째 줄에 S가 주어진다.

출력

S에 P(N)이 몇 군데 포함되어 있는지 출력한다. (P(N) 끼리 겹칠 수 있음)

알고리즘

// KMP 알고리즘을 응용했다.

while(i=0;i<m;++i)
{
	if(이전에 P(N)을 찾았다면)
    	if(앞의 두 문자가 "OI"라면)
        	count++;
        else
        	continue;
    else
    	for(int j=0;j<P(N).size();++j)
        	if(일치하지 않는다면)
            	i+=j;
        if(P(N)을 찾았다면)
        	count++;
}

코드

#include <iostream>
#include <string>

using namespace std;

int main() 
{
	int n, m, cnt = 0;
	string s;
	cin >> n >> m >> s;

	int cmp_len = 1 + 2 * n;
	bool prev_cmp = false;

	for (int i = 0; i < m - 1;)
	{
		if (prev_cmp)
		{
			if (s[i] == 'O' && s[i + 1] == 'I')
			{
				++cnt;
				i += 2;
			}
			else
			{
				prev_cmp = false;
			}
		}
		else
		{
			bool is_crt = true;

			for (int j = 0; j < cmp_len; ++j)
			{
				if (j % 2 == 0)
				{
					if (s[i + j] != 'I')
					{
						is_crt = false;
						i += j + 1;
						break;
					}
				}
				else
				{
					if (s[i + j] != 'O')
					{
						is_crt = false;
						i += j;
						break;
					}
				}
			}

			if (is_crt)
			{
				++cnt;
				prev_cmp = true;
				i += cmp_len;
			}
		}
	}
    
	cout << cnt;
	return 0;
}

마치며

 지난 학기 수강했던 자료구조에서 배운 KMP 알고리즘이 생각나서 조금 응용해서 해결해 봤습니다. 학교를 다니며 배운 지식이 사용되니까 뭔가 수업 열심히 듣길 잘했다는 생각이 듭니다.