Hoof, Paper, Scissors (Silver)

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

14453번: Hoof, Paper, Scissors (Silver)

이번 문제는 prefix sum 문제 입니다.

하나의 구간에 H / P / S 중 가장 많은 것의 수 또는

두 구간으로 나눴을 때 (왼쪽에서 H / P / S 중 가장 많은 것의 수) + (오른쪽에서 H / P / S 중 가장 많은 것의 수)

모든 구간에 대해서 시행해서 가장 큰 값과

 

위에서 하나의 구간에 대해서 시행한 것 중 큰 값을 출력하면 됩니다.

H / P / S 중 하나를 입력받고, prefix sum을 계속적으로 시도해주면 됩니다.

 

 

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <string>
#include <string.h>
 
#define endl    '\n'
#define FastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
using namespace std;
 
int n;
struct tt {
    int h, p, s;
};
vector<tt> seq;
 
int main() {
    FastIO;
 
    cin >> n;
 
    seq.resize(n + 1, { 0,0,0 });
    for (int i = 1; i <= n; i++) {
        char c;
        cin >> c;
        if (c == 'P') seq[i].p += 1;
        else if (c == 'H') seq[i].h += 1;
        else seq[i].s += 1;
        seq[i].h += seq[i - 1].h;
        seq[i].p += seq[i - 1].p;
        seq[i].s += seq[i - 1].s;
    }
    
    int ans = max(seq[n].h, max(seq[n].p, seq[n].s));    // 구간을 하나도 안나눴을 때
 
    for (int i = 2; i <= n; i++) {                        // 구간을 나누기 
        int left = max(seq[i - 1].h, max(seq[i - 1].p, seq[i - 1].s));
        int right = max((seq[n].h - seq[i - 1].h), max((seq[n].p - seq[i - 1].p), (seq[n].s - seq[i - 1].s)));
        ans = max(ans, (left + right));
    }
 
 
    cout << ans;
 
 
 
    return 0;
}