백준 26156 (C++) 나락도 락이다

최초 업로드: 2025-10-03 07:28:13

최근 수정 시간: 2025-10-03 07:28:13

게시자: rlatjwls3333

카테고리: 백준

# [Gold III] 나락도 락이다

[문제 링크](https://www.acmicpc.net/problem/26156)

## 문제 설명

알파벳 대문자로 이루어진 길이 $N$의 문자열 $S$가 주어진다. $S$의 부분열 중 ROCK으로 끝나는 문자열의 개수를 $10^9+7$로 나눈 나머지를 출력하라.

## 입력

첫 번째 줄에 문자열 $S$의 길이 $N$이 주어진다. $(4 \leq N \leq 1\ 000\ 000)$

두 번째 줄에 알파벳 대문자로만 이루어진 문자열 $S$가 주어진다.

## 출력

$S$의 부분열 중 ROCK으로 끝나는 문자열의 개수를 $10^9 + 7$로 나눈 나머지를 출력한다.

## 노트
문자열의 부분열이란 문자열에서 몇몇 문자를 지운(물론 지우지 않아도 된다) 문자열을 의미한다. 예를 들어 aan은 hanyang의 부분열이다.

## 풀이
뒤에서부터 K, CK, OCK 개수를 기억하며 R 위치마다 $2^i$ * cnt[OCK]을 더해주면 됩니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD = 1e9+7;

ll cnt[3]; // OCK, CK, K의 등장 횟수

ll expo_pow(ll a, ll b) {
    if(b==0) return 1;
    ll tmp = expo_pow(a, b/2);
    if(b%2) return tmp*tmp%MOD*a%MOD;
    return tmp*tmp%MOD;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; string s; cin >> n >> s;

ll total=0;
 for(int i=n-1;i>=0;i--) {
 if(s[i]=='K') cnt[2] = (cnt[2]+1)%MOD;
 else if(s[i]=='C') cnt[1] = (cnt[1]+cnt[2])%MOD;
 else if(s[i]=='O') cnt[0] = (cnt[0]+cnt[1])%MOD;
 else if(s[i]=='R') total = (total+expo_pow(2, i)*cnt[0])%MOD;
 }
 cout << total;
}
```