fragment-header
fragment-markdown
홈
로그인
로그아웃
내 블로그
설정
로그인
백준 26156 (C++) 나락도 락이다
최초 업로드: 2025-10-03 07:28:13
최근 수정 시간: 2025-10-03 07:28:13
게시자: rlatjwls3333
카테고리: 백준
조회수: 13
# [Gold III] 나락도 락이다 [문제 링크](https://www.acmicpc.net/problem/26156) ## 문제 설명 <blockquote> <p style="text-align: center;"><strong>나락도 락이다. 부모님께 온 연락도 락이다. 오락가락?도 락? 이다.?</strong></p> </blockquote> <p>알파벳 대문자로 이루어진 길이 $N$의 문자열 $S$가 주어진다. $S$의 부분열 중 <strong>ROCK</strong>으로 끝나는 문자열의 개수를 $10^9+7$로 나눈 나머지를 출력하라.</p> ## 입력 <p>첫 번째 줄에 문자열 $S$의 길이 $N$이 주어진다. $(4 \leq N \leq 1\ 000\ 000)$</p> <p>두 번째 줄에 알파벳 대문자로만 이루어진 문자열 $S$가 주어진다.</p> ## 출력 <p>$S$의 부분열 중 <strong>ROCK</strong>으로 끝나는 문자열의 개수를 $10^9 + 7$로 나눈 나머지를 출력한다.</p> ## 노트 <p>문자열의 부분열이란 문자열에서 몇몇 문자를 지운(물론 지우지 않아도 된다) 문자열을 의미한다. 예를 들어 aan은 hanyang의 부분열이다.</p> ## 풀이 뒤에서부터 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; } ```