c언어 11059번 크리 문자열 (백준)

 

#include <stdio.h>
#include <string.h>
int main(void)
{
	char s[1001]; //문자열을 받을 배열
	int arr[1001] = {}; //누적합을 저장할 배열
	
	scanf("%s",s);
	
	int len = strlen(s); //문자열의 길이
	int ans = len - (len&1); //특정 길이의 문자열을 비교하기위한 수, 처음엔 문자열의 길이/2
	
	for(int i=1; i<=len; i++) { //누적합을 구합니다.
		arr[i] = arr[i-1] + (s[i-1]-'0');
	}
	
	while(ans) {
		ans--; //크리 문자열의 절반을 1씩 줄입니다.
		int tmp = len - ans; 
		for(int i=ans; i<=tmp; i++) {
			if(2*arr[i] == arr[i+ans]+arr[i-ans]) { //arr*2 크기의 문자열을 절반으로 나눠 왼쪽과 오른쪽 문자열의 합이 같은지를 파악합니다.
				printf("%d", ans*2); //같다면 크리 문자열의 절반에 *2을 합니다.
				return 0; //같다면 종료합니다.
			}
		}
	}
}

 

풀이 : 누적합

 

문자열을 받은 다음

이를 따로 정수형 배열에 누적합을 구해서 저장합니다 ([0] 은 0 으로 둡니다)

 

크리 문자열의 최댓값은 처음 문자열의 길이를 2로 나누었을때의 몫입니다.

크리 문자열인지를 확인하기 위해선 크리 문자열의 절반을 기준으로 양쪽의 합이 같은지를 비교해야 합니다.

 

ans 는 크리 문자열을 확인하기위해서 크리 문자열의 절반의 값을 담는 변수입니다. 초기값은 문자열의 크기를 2로 나눴을 때의 몫입니다.

 

크리 문자열의 절반의 크리를 ans로 둔 상태로 왼쪽 오른쪽의 합을 비교하며, 만약 없다면

ans의 값을 1 감소시켜서 다시 크리 문자열이 있는지를 확인합니다.

 

만약 왼쪽 오른쪽의 문자열이 값이 같은 경우 프로그램을 종료합니다.

 

 

https://www.acmicpc.net/problem/11059

11059번: 크리 문자열