백준 16139

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

16139번: 인간-컴퓨터 상호작용

누적합문제였습니다.

 

처음 입력 받을 때부터 앞에 해당 알파벳이 몇 개 있는 지 확인 후, 해당 위치에 그 알파벳이 있으면 +1, 아니면 그냥 가져갑니다. 그리고 쿼리 시, l번째에 해당 알파벳이 있다면 dp[r] - dp[l] + 1, 없다면 dp[r] - dp[l] 을 하면 됩니다. 

(몇 가지 케이스를 그려보면 쉽게 구할 수 있습니다.)

 

코드는 다음과 같습니다.

#include <iostream>
#include <string>
#include <cstring>

using namespace std;

string S;
int q, l, r;
char c;

int dp[200000][26]; // 알파벳 26개

void init()
{
    cin >> S;
    cin >> q;
    memset(dp, 0, sizeof(dp));
}

void calc()
{
    dp[0][S[0] - 'a'] = 1;
    
    for(int i = 1; i < S.size(); i++) {
        int idx = S[i] - 'a'; // 소문자로만 구성
        for(int j = 0; j < 26; j++) {
            dp[i][j] = dp[i - 1][j];
        }
        dp[i][idx] = dp[i - 1][idx] + 1;
    }
}

void query()
{
    cin >> c >> l >> r;
    
    // case1 : S[l] != c && S[r] != c || S[l] != c && S[r] == c 
    if(S[l] != c) {
        cout << dp[r][c - 'a'] - dp[l][c - 'a'] << '\n';
    }
    
    // case2 : S[l] == c && S[r] != c || S[l] == c && S[r] == c 
    else {
        cout << dp[r][c - 'a'] - dp[l][c - 'a'] + 1 << '\n';
    }
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    init();
    calc();
    while(q--) {
        query();
    }
}