[코드포스 Practice9] D. Minimum number of steps

We have a string of letters 'a' and 'b'. We want to perform some operations on it. On each step we choose one of substrings "ab" in the string and replace it with the string "bba". If we have no "ab" as a substring, our job is done. Print the minimum number of steps we should perform to make our job done modulo 109 + 7.

The string "ab" appears as a substring if there is a letter 'b' right after the letter 'a' somewhere in the string.

Input
The first line contains the initial string consisting of letters 'a' and 'b' only with length from 1 to 106.

Output
Print the minimum number of steps modulo 109 + 7.

---

ㅋㅋ진짜 이게 뭐야 싶은 문제였다.

 

보니깐 b는 다 앞으로 a는 다 뒤로 가야 끝이 나는 건 알겠는데 횟수를 어떻게 세야할지 막막했다. 그래서 막 고민하다가 a와 b의 자리가 뒤바뀌어서 문젠가 싶어서 자리가 바뀐 거 개수 세서 제곱수로 만들어줬음. 왜 제곱수냐면 보니깐 제곱수인 것 같아서.. 아무튼 근거도 없고 틀렸을꺼란 삘이 들었지만 제출했고 틀렸다. 보니깐 1번 답이 3이었다.

 

 

음.. b는 항상 2배로 늘어나고 변환 횟수는 b 개수를 세는 거라 위와 같이 숫자가 변하면 될꺼라 생각했다. 

그래서 아래와 같이 코딩했는데 틀렸네..

원인을 모르겠어서 다시 찾아봐야겠다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
 
using namespace std;
using i64 = long long;
 
int main() {
    string s;
    cin >> s;
    i64 count = 0, b = 0;
    int state = 0;
    
    for(int i = s.size()-1; i>= 0; i--){
        if(state == 0 && s[i]=='b'){
            state = 1;
            b++;
        }
        else if(state == 1){
            if(s[i] == 'a'){
                count += b;
                b *= 2;
            }
            else {
                b++;
            }
        }
    }
    
    cout << count;
    
    return 0;
}

 

 

뭐가 문제지??? 맞는 것 같은데 어디가 문제인지 모르겠다.

abbaaabaabaaaaabbbbaababaaaaabaabbaaaaabbaabbaaaabbbabbbabb

 

예제 여기서만 틀림

처음에는 오버플로우 때문에 그런갑다 했는데 longlong으로 바꿔도 틀림.. 뭐지????

 

---

결국 북님 코드 봤다. 알고보니 문제에서 mod 뭐라뭐라 했는데 뭐지 하고 넘겼던게 문제였다. 답 mod 취하라 한겨... 음.. 허허 ㅎㅎ;; 문제를 잘 읽읍시다

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#define MOD ((i64)1e9 + 7)
using namespace std;
using i64 = long long;
 
int main() {
    string s;
    cin >> s;
    i64 count = 0, b = 0;
    int state = 0;
    
    for(int i = s.size()-1; i>= 0; i--){
        if(state == 0){
            if(s[i]=='b'){
                state = 1;
                b++;
            }
        }
        else if(state == 1){
            if(s[i] == 'a'){
                count += b;
                b *= 2;
            }
            else {
                b++;
            }
        }
        
        b %= MOD;
        count %= MOD;
    }
    
    cout << count;
    
    return 0;
}

 

MOD로 나눠줬더니 맞았다. 예헤이