지렁이게임, 문제 해결 훈련

문제

지렁이게임을 하자. 지렁이게임은 가장 긴 지렁이를 만드는 게임이다. 지렁이는 1과 0으로 이루어져있고 1과 0이 연속되어 있어야한다. 예를들어 0101은 길이 4짜리 지렁이이다. 0110은 지렁이가 될 수 없고 01과 10 각각 길이 2짜리 지렁이가 될 수 있다. 0과 1의 Input이 주어질때 참가자는 한가지 구간을 변경하여 지렁이를 만들 수 있다.

아래의 표를 보자

길이 10짜리 input이 주어질때 1,2 idx의 input을 바꾸면 참가자가 만들 수 있는 가장 긴 지렁이는 길이 7짜리 지렁이이다.

지렁이 게임에서 참가자가 만들 수 있는 가장 긴 지렁이를 구하라.

 

입력

지렁이를 구성하는 input의 갯수 N을 입력받는다.

N개만큼 1과 0이 입력된다.

N은 2이상 100000이하이다.

 

10

1 1 0 0 1 0 1 1 1 0

 

출력

7

 

---

문제해결

모든 경우의 수로 해결할 수 있을까? 각각의 idx마다, 값을 변경하고 길이도 가변적으로 모든 경우의 수를 구하는 것이다. 가능할 수는 있겠으나 경우의 수가 너무 많고 구현하기도 쉽지 않을 것이다. 무엇보다 N이 100000이기 때문에 시간복잡도가 매우 높아질 것이다.

조합, 순열, DFS, BFS도 아니다. 그렇다면 어떻게 해결할 수 있을까?

이런 문제에서는 특정 규칙을 찾아야한다. 아래를 따라가보자

1) 입력된 input은 그 상태로서 여러개의 지렁이로 구성된다.

2) 같은 숫자가 연속되면 각기 독립적인 지렁이로 구분할 수 있다.

3) 연속된 지렁이가 3개 있을때 가운데 지렁이의 input을 바꾸면 연속된 3개의 지렁이는 하나의 긴 지렁이가 된다.

 

따라서 입력된 input에서 독립된 지렁이 개수와 길이를 구하여 따로 저장해놓자.

가운데 지렁이만 변환하면 하나의 지렁이가 되므로, 3개의 지렁이 합이 만들어진 지렁이의 길이다.

독립된 3개의 연속하는 지렁이의 합이 가장 큰 길이가 정답일 것이다.

 

위의 case를 지렁이로 나누면 아래 그림 처럼 5개의 지렁이로 나뉠 수 있다. 즉, 동일한 숫자가 연속

으로 오면 독립된 지렁이로 구분할 수 있다. 여기서 연속된 3개의 지렁이의 총합이 가장 긴 길이를 구하면 되는 것이다.

 

그러나 모든 경우에 가능할까? 예외는 없을까?

N이 3이고, input이 001이면 어떻게 할 것인가? 지렁이는 총 2마리다. 길이1짜리 0지렁이, 길이2짜리 01지렁이.

이런 경우에는 둘중 하나를 변환해주면 최종 가장 긴 길이가 될 것이다.

 

주어진 Input의 독립 지렁이의 개수가 3보다 작을 때에는 2개 지렁이의 합이 답일 것이다.

 

#include <stdio.h>

int N;
int WORM[100000+100];
int cnt=0;
int PTN[100000+100];
int ans=0;

void Input(){
	scanf("%d",&N);
	for(int i=0; i<N; i++)
	{
		scanf("%d", &WORM[i]);
	}
}

void Solve()
{
	int i=0;
	int cnt =0;
	int len=1;
	
	for(i=0; i<N-1; i++)
	{
		if(WORM[i] != WORM[i+1]) len++;
		else
		{
			PTN[cnt++]=len;
			len=1;
		}
	}
	PTN[cnt++]=len;

	//printf("cnt : %d\n",cnt);
	
	if(cnt>=3)
	{
		int sum=0;
		for(int i=0; i<=cnt-3; i++)
		{
			for(int j=i; j<=i+2; j++)
			{
				sum+=PTN[j];
			}
			if(sum>ans) ans = sum;
			sum=0;
		}
	}
	else
	{
		ans=PTN[0]+PTN[1];
	}
	
}

int main() {
	Input();
	Solve();
	printf("%d",ans);
	return 0;
}