백준 31846 - 문자열 접기(C++ )

문제 링크입니다. https://www.acmicpc.net/problem/31846

 

문자열이 하나 주어지고, 범위가 주어졌을 때, 주어진 범위를 잘 접어서 최대로 겹치는 문자 수를 구하려고 합니다.

 

먼저, 문자열의 길이와 주어지는 범위의 수가 적기에 모든 경우를 확인해봐도 시간초과가 되지 않습니다.

 

따라서, 문자열을 하나만 뒤집었을 때, 2개만 뒤집었을 때, 3개만 뒤집었을 때, ... N개를 뒤집었을 때를 전부 확인해봐서

문자가 얼마나 겹치는지를 직접 확인해주면 됩니다.

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>

using namespace std;

int N, M;
char arr[55];

void solve() {
	for (int i = 1; i <= M; i++) {
		int x, y;
		cin >> x >> y;
		int st = x;
		int ans = 0;
		while (1) {
			if (st == y) break;
			string k1 = "", k2 = "";
			int cnt = 0;
			for (int j = x; j <= st; j++) {
				k1 += arr[j];
			}
			for (int j = st + 1; j <= y; j++) {
				k2 += arr[j];
			}
			reverse(k1.begin(), k1.end());
			for (int j = 0; j < min(k1.size(), k2.size()); j++) {
				if (k1[j] == k2[j]) cnt++;
			}
			ans = max(ans, cnt);
			st++;
		}
		cout << ans << "\n";
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> arr[i];
	cin >> M;
	solve();
	return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.