c언어 5525번 IOIOI (백준)

#include <stdio.h>

int main(void)
{
	int n;
	scanf("%d", &n);
	
	int m;
	scanf("%d", &m);
	char arr[m+1];
	
	scanf("%s", arr); //문자열 입력

	int cnt = 0;
	int len = 0; //P(n)을 이루는 문자열의 길이
	int ans = 0;
	for(int i=0; i<m; i++) {
		if(len == 0 && arr[i] == 'I') len++; //첫번째 I, P()의 길이를 1로 시작한다.
		else if(len & 1 && arr[i]=='O') len++; //바로앞에 I가 있다면 P()의 길이를 늘린다.
		else if(len%2==0 && len>=2 && arr[i]=='I') { //P()의 길이가 2 이상이며, 짝수 길이이며, 이전이 O이고, 이번것이 I 일때 P()의 길이를 1 늘린다.
			len++;
			cnt++;
		} else if(len>=2) { //P()을 더이상 길게 할 수 없는 경우, 이전까지의 P()의 길이를 이용하여, P(n)의 개수를 구한다.
			if(cnt >= n) ans += (1 + (cnt-n)); 
			cnt = 0;
			len = 0;
		} 
		if(len == 0 && arr[i] == 'I') len++; //첫번째 I, P()의 길이를 1로 시작한다.
        //28줄 코드가 18줄에도 있고 여기에도 있는 이유는 IOIIOI 이런 경우 처럼
        //P()이 더이상 안 만들어지는 경우에는 ...OO... 나 ...II...가 있으며, ...II...인 경우 두번째 I에서 새로운 P()이 시작 할 수 있기 때문이다
	}
	//반복문이 끝나버려서, 구한 P()을 이용하여 P(n)의 개수를 ans에 누적하지 못한 경우를 위해 적었다.
	if(cnt >= n) ans += (1 + (cnt-n)); 
	printf("%d", ans);
    return 0;
}

 

 

IOI.... 개수 구하는 법

 

하나의 문자에서 IOI....가 어디까지 되는지를 구하고,

다음 문자에서 IOI...가 어디까지 되는지를 구하고, ...

이런식으로 문자 한개씩을 시작점으로 보고 만들 수 있는 IOI를 구해도 되나, -> 길이가 늘어나면 걸리는 시간이 많이 걸린다.

 

 

---------------------------------------------

 

IOIOI = P(2)은 IOI = P(1)가 2개이다.

 

IOIOIOI = P(3)은 IOIOI = P(2)가 2개, IOI = P(1) 가 3개이다.

 

즉

 

P(n) 1개 = P(n-1)+1 개이며

P(n) 1개 = P(m) n-m+1개 이다. (단 n,m 은 자연수 및 n>=m)

 

이 경우엔 IOI....로 이루어진 문자열을 구하면(P()) 바로 P(n)으로 변환해서 누적하면 한번만 모든 문자열을 훍기만 하면

구하는 시간이 N(문자열의 길이) 밖에 걸리지 않을 정도로 위보다 빨리 구할 수 있게 된다.