BOJ11986 스탬프렐리-2

문제 링크 : BOJ11986

문제 요약

J, O, I로 이루어진 이루어진 문자열이 주어진다. 이 때 문자 하나만 추가하여 부분문자열 (Subsequence)중에서 "JOI"의 개수가 최대가 되도록 해야한다.

예제 1

5
JOIOI

의 경우 앞에 J를 붙여 6개를 만들 수 있다.

문제 풀이

추가하는 문자가 J인 경우 제일 앞에 붙이는게 이득이고 추가하는 문자가 I인 경우 제일 뒤에 붙이는게 이득이다. 만약 O를 추가해야 하는경우라면 추가된 기준으로 (왼쪽에 있는 J의 개수) * (오른에 있는 I의 개수) 만큼 추가 된다.

우선 경우의 수를 계산하는 함수를 calc라 하고 기존의 문자열을 S라고 하자. 추가로 count(i, j, c)는 i번째 문자와 j번째 문자 사이에 있는 문자 c의 개수라고 하자.

calc은 간단한 \( O(n) \) DP, count(i, j, c)는 전처리 후 \( O(1) \) 만에 구할 수 있다.

답은
$$ max(calc('J'+S), calc(S) + count(1, i, 'J') * count(i, n, 'I'), calc(S + 'I')) $$

소스코드 (C++11)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll calc(string s)
{
    ll j=0, o=0, i=0;
    for(char c : s)
    {
        if(c == 'J') j++;
        else if(c == 'O') o += j;
        else if(c == 'I') i += o;
    }
    return i;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    string s; cin >> s;
    ll res = 0, base = calc(s);
    int j=0, i=count(s.begin(), s.end(), 'I');
    for(char c : s)
    {
        if(c == 'J') j++;
        else if(c == 'I') i--;
        res = max(res, base + 1LL*j*i);
    }
    cout << max({res, calc("J"+s), calc(s+"I")}) << endl;
    return 0;
}