[Atcoder]Attention

문제링크

사람의 번호를 0부터 n-1까지 있다고 하고, 기준인 사람을 j라고 하자. 그렇다면 0부터 j-1번째 사람 중 서쪽을 보고 있는 사람은 동쪽을 봐야하며, J+1번째 사람부터 n-1번째 사람 중 동쪽을 보고 있는 사람은 서쪽을 바라보게 해야 한다. 즉 각 기준 j를 움직이며 움직일 사람들의 수를 조사해야 하는데 구간 합 알고리즘(prefix sum)을 이용해서 전처리하면 시간복잡도 O(N) 만에 풀 수 있다.

구현에서 자꾸 틀려서 기준이 가장 왼쪽 일때와 오른쪽일때는 따로 빼주었다.

#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
 
int prefix_w[300001];
int prefix_e[300001];
 
int main()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    if (s[0] == 'E')
        prefix_e[0] = 1;
    else
        prefix_w[0] = 1;
    for (int i = 1; i < n; i++) {
        if (s[i] == 'E') {
            prefix_e[i] = prefix_e[i - 1] + 1;
            prefix_w[i] = prefix_w[i - 1];
        }
            
        else if (s[i] == 'W') {
            prefix_w[i] = prefix_w[i - 1] + 1;
            prefix_e[i] = prefix_e[i - 1];
        }
            
    }
    int ans = 987654321;
    for (int i = 1; i < n - 1; i++) {
        int tot = prefix_w[i - 1] + prefix_e[n - 1] - prefix_e[i];
        if (ans > tot)
            ans = tot;
    }
    ans = min(ans, prefix_e[n - 1] - prefix_e[0]);
    ans = min(ans, prefix_w[n - 2]);
    cout << ans;
    return 0;
        
 
}