[BOJ/Bronze 1] 백준 11059 크리 문자열(C++)

문제 링크

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

11059번: 크리 문자열

 

문제

숫자로만 이루어진 문자열 S가 주어진다. S의 연속된 부분 문자열 중에서 길이가 짝수이고, 앞의 절반의 합과 뒤의 절반의 합이 같은 부분 문자열을 크리 문자열이라고 한다. 빈 문자열은 크리 문자열이 아니다.

S의 크리 문자열 중에서 가장 길이가 긴 것을 찾는 프로그램을 작성하시오.

예를 들어 S = "67896789" 인 경우에 정답은 "67896789"이 된다. 또, S = "6789789" 인 경우에 정답은 "789789"가 된다. S = "6789678" 인 경우에 정답은 "9678" 이다.

입력

첫째 줄에 문자열 S가 주어진다. S는 숫자로만 이루어져 있으며, 길이는 1,000을 넘지 않는다. 항상 크리 문자열이 존재하는 입력만 주어진다.

출력

첫째 줄에 S의 크리 문자열 중에서 가장 긴 것의 길이를 출력한다.

예제 입력 1

67896789

예제 출력 1

8

예제 입력 2

6789789

예제 출력 2

6

예제 입력 3

6789678

예제 출력 3

4

알고리즘 분류

• 문자열
• 누적 합

풀이

1~N번째 숫자를 시작점으로 하여, 문자열의 끝까지 누적 합을 먼저 구하였다.

그리고 문자열의 특정 구간에서, 구간 전체의 합이 짝수이고, 구간 전체의 합과 구간 전체 중 앞부분 절반의 합이 2배 차이라면 그 문자열은 크리 문자열이라고 간주하고 길이의 최댓값을 갱신해주었다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 1001
#define LL long long
#define INF 1e9

using namespace std;
string S;
int Sum[MAX][MAX];
int Answer = 0;

void Input() {
	cin >> S;
}

void Settings() {
	for (int i = 0; i < S.size(); i++) {
		Sum[i][i] = (S[i] - '0');
		for (int j = (i + 1); j < S.size(); j++) {
			Sum[i][j] = Sum[i][j - 1] + (S[j] - '0');
		}
	}
	for (int i = 0; i < S.size(); i++) {
		int IDX = i;
		for (int j = (i + 1); j < S.size(); j += 2) {
			if ((Sum[i][j] % 2 == 0) && ((Sum[i][j] / 2) == Sum[i][IDX])) {
				Answer = max(Answer, j - i + 1);
			}
			IDX++;
		}
	}
}

void Find_Answer() {
	cout << Answer << "\n";
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}