백준 31846

문제

기다란 종이에 알파벳 대문자로만 이루어진 문자열이 한 줄로 쓰여 있다. 예를 들어 아래 그림과 같이 종이에 “ABAACA”가 쓰여 있다고 가정하자.

 

이제 이 종이를 한 번만 접을 것이다. 종이는 서로 이웃한 문자 사이에서만 접을 수 있다. 예를 들어 아래 그림과 같이 위 종이를 4번째 문자와 5번째 문자 사이에서 접을 수 있다.

 

이때 서로 맞닿은 문자 쌍 중에서, 서로 같은 문자가 맞닿은 쌍의 개수가 이 접기의 점수가 된다. 예를 들어 앞에서의 접기의 점수는 1점이 된다. 하지만 아래 그림과 같이 3번째 문자와 4번째 문자 사이에서 종이를 접으면 점수는 2$점이 된다.

 

이제 여러분은 알파벳 대문자로만 이루어진 문자열 𝑆$ S $가 주어질 때, 다음과 같은 질문 𝑄개에 답해야 한다.

•  𝑙 𝑟$: 문자열 𝑆의 𝑙번째 문자, (𝑙+1)번째 문자, ⋯, 𝑟번째 문자가 차례대로 종이에 쓰여 있을 때, 종이를 한 번 접어서 얻을 수 있는 최대의 점수는 몇 점인가?

풀이

문자 사이에서만 접을 수 있다는 것에 초점을 두자.

1 - 6인 경우를 생각해보면 접을 수 있는 경우는

1과 2 사이를 접어서 [1, 2]를 검사하는 경우

2와 3 사이를 접어서 [1, 4]를 검사하는 경우

3과 4 사이를 접어서 [1, 6]을 검사하는 경우

4와 5 사이를 접어서 [3, 6]을 검사하는 경우

이렇게 시작점부터 2 * n개의 문자에서 시작 문자와 끝 문자가 같은지, 끝점부터 2*n개의 문자에서 시작문자와 끝 문자가 같은지를 판별해 개수를 세면 된다.

 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string s;
int N, Q;
int solve(int l, int r) {
    int ans1 = 0, ans2 = 0, ans=0, size_idx = 1;
    while((r-l)+1 >= size_idx * 2) {
        int l1 = l, r1 = size_idx*2 -1 + l;
        while(l1 < r1) {

            if(s[r1] == s[l1]) ans1 += 1;
            l1 += 1; r1 -= 1;
        }
        int l2 = r-(size_idx*2-1), r2 = r;
        while(l2 < r2) {
            
            if(s[r2] == s[l2]) ans2 += 1;
            l2 += 1; r2 -= 1;
        }
        ans = max(max(ans1, ans2), ans);
        ans1 = 0; ans2 = 0;
        size_idx += 1;
    }
    return ans;
}
int main(){
    cin>>N>>s>>Q;
    for(int i=0; i<Q; i++){
        int l, r; cin>>l>>r;
        cout<<solve(l-1, r-1)<<'\n';
    }


}