R621(Div.1+Div.2) C. Cow and Message

 

A,B,C중에 오히려 가장 쉬운 문제가 아니였나 싶다(?)

 

문제 자체 이해는 어려웠다

S라는 문자열 안에서 등차수열로 이루어진 T라는 문자열을 숨겼다

이 때 문자열 T의 수들 중 최댓값을 찾는 문제다

 

생각하다보면 문제가 쉬워진다

 

한번 정리를 해보자

1. 길이가 1일 때 => max(alpha[26]) 중 하나다

2. 길이가 2일 때 => for문을 통해 입력받으면서 보면 된다max(d[26][26])

3. 길이가 3일 때 => 여기부터 생각해봐야한다 꼭 봐야할까?

길이가 3이상이라면 길이가 2인것들을 무조건 포함해야만 만들 수 있다

따라서 볼 필요가 없다! 2까지만 보면 된다!

 

그럼 바로 쉬운문제로 변한다!

 

문제에서 필요로 하는것들만 뽑아내는 능력이 이럴때 쓰이는건가..!

이 문제는 쉬워서 다행히 잘 보였다..!

 

소스코드

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
#define ll long long
string s;
ll alpha[26];
ll d[26][26];
 
int main() {
    cin >> s;
    int sz = s.size();
    for (int i = 0; i < sz; i++) {
        for (int j = 0; j < 26; j++) {
            if (alpha[j]) d[j][s[i] - 'a'] += alpha[j];
        }
        alpha[s[i] - 'a']++;
    }
    ll ans = 0;
    for (int i = 0; i < 26; i++) ans = max(ans, alpha[i]);
    for (int i = 0; i < 26; i++) {
        for (int j = 0; j < 26; j++) {
            ans = max(ans, d[i][j]);
        }
    }
    printf("%lld\n", ans);
}