[백준] 24956번 : 나는 정말 휘파람을 못 불어 (C++)

24956번 : 나는 정말 휘파람을 못 불어

---

문제)

휘파람을 불지 못하는 시루는 휘파람을 불기 위해 수없이 많이 시도했지만 항상 실패한다. 시루의 휘파람 연습을 도와주고 있는 루시는, 시루가 휘파람과 비슷한 소리를 낼 때마다 사탕을 주기로 했다.

시루의 입에서 나온 소리는 대문자로 구성된 문자열 S로 나타낼 수 있다. 루시는 문자열 S에서 휘파람과 비슷한 소리, 즉 '유사 휘파람 문자열'의 개수를 구해야 한다. '유사 휘파람 문자열'은 다음과 같이 정의한다.

• WHEE는 '유사 휘파람 문자열'이다.
• '유사 휘파람 문자열' 뒤에 E를 붙인 것 또한 '유사 휘파람 문자열'이다.

'유사 휘파람 문자열'은 문자열 S 상에서 연속하지 않아도 된다. 즉, S에서 '유사 휘파람 문자열'인 부분 수열(subsequence)의 개수를 구하면 된다.

시루는 수없이 많이 시도했기 때문에 S의 길이가 너무 길어졌다. 루시를 도와 시루에게 사탕을 몇 개 줘야 할지 계산해주자.

 

 

 

입력 :

첫째 줄에 문자열 S의 길이 N이 주어진다.

둘째 줄에 대문자로만 구성된 문자열 S가 주어진다.

 

 

출력 :

'유사 휘파람 문자열'인 부분 수열의 개수를 1000000007(=10^9+7)로 나눈 나머지를 출력한다.

 

 

 

 

 

 

풀이)

 

// 24956. 나는 정말 휘파람을 못 불어
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#define MOD 1000000007
 
using namespace std;
 
// 2의 거듭제곱을 모듈러해
// 미리 배열에 담아놓는다.
vector<int> _pow;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n;
    cin >> n;
 
    string word;
    cin >> word;
 
    vector<int> prefixE(n + 1, 0);
    vector<int> prefixW(n + 1, 0);
    for (int i = 1; i < n + 1; i++)
    {
        if (word[i - 1] == 'E') prefixE[i]++;
        if (word[i - 1] == 'W') prefixW[i]++;
        prefixE[i] += prefixE[i - 1];
        prefixW[i] += prefixW[i - 1];
    }
 
    _pow.push_back(0);
    long long temp = 1;
    for (int i = 1; i <= prefixE[prefixE.size() - 1]; i++)
    {
        temp *= 2;
        temp %= MOD;
        _pow.push_back(temp);
    }
 
    long long answer = 0;
    for (int i = 1; i < n + 1; i++)
    {
        if (word[i - 1] == 'H')
        {
            int wCnt = prefixW[i];
            int eCnt = prefixE[n] - prefixE[i];
 
            // 거듭제곱 빠르게 구하기
            long long temp = _pow[eCnt];
            temp = temp - (eCnt + 1);
 
            if (temp < 0) temp = 0;
 
            answer += (wCnt * temp);
            answer %= 1000000007;
        }
    }
 
    cout << answer;
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/24956 

24956번: 나는 정말 휘파람을 못 불어