어떤 배열을 양쪽으로 확인해 나가기

길이 N짜리 배열이 있을 때, 여기서 어떤 가운데 지점을 고르고, 그걸 기준으로 왼쪽과 오른쪽을 비교하고자 한다.

 

출처 백준 31846

 

구현은 간단하다.

1. 어떤 가운데 지점을 start 부터 시작해, end-1 까지로 잡는다.

2. 해당 start 를 기준으로 + 쪽이 right, - 쪽이 left 라고 가정하고 (start, end) 사이에 있도록 해준채 무식하게 비교하면 된다

 

문제를 풀어보자

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

 

#include<iostream>
#include<vector>
#include<string>
using namespace std;
int N, t;
string s;
vector<int> items;
int do_search(int start, int end) {
	int ans = 0;
	int m = start;
	for (int m = start; m < end; m++) {
		int cnt = 0;
		int right = m + 1;
		int left = m;
		while (right <= end && left >= start) {
			if (items[right] == items[left]) {
				cnt++;
			}
			right++;
			left--;
		}
		ans = (ans < cnt) ? cnt : ans;
	}
	return ans;
}


int main() {
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> N;
	cin >> s;
	items.push_back(0);
	for (char i : s) {
		items.push_back(int(i));
	}
	cin >> t;
	for (int i = 0; i < t; i++) {
		int start, end;
		cin >> start >> end;
		cout << do_search(start, end) << "\n";
	}

	return 0;
}

 

참고로 이 문제는 DP로도 풀 수 있어요