[SWEA] 7853 오타

문제

SWEA 7853 : 오타

SW Expert Academy

접근

재경이는 i번째 문자에 i - 1번째 문자 또는 i번째 문자 또는 i + 1번째 문자를 칠 수 있다.

따라서 [i - 1], [i], [i + 1]이 모두 다른 단어로 이뤄져 있으면 i번째에 위치할 문자의 경우의 수는 3이 된다.

[i - 1], [i], [i + 1] 중 두 문자가 같다면 경우의 수는 2가 되며 셋 다 같을 경우는 1이 된다.

따라서 i번째에 위치할 문자의 경우의 수를 계속 곱해나가면 된다.

여기서 0번째 문자는 i - 1번째 문자가 없기 때문에 i번째와 i + 1번째 문자만을 보면 되고, 마지막 문자는 i - 1번째와 i번째 문자만을 봐주면 된다.

그리고 출력 시에 답에서 10억7로 나눈 나머지를 출력하라는 조건이 있다.

이때 for문을 돌며 경우의 수를 전부 곱해나간 뒤 마지막 출력 시에만 %10억7을 해주면 당연히 overflow가 날 수밖에 없다. 가능한 경우의 수의 최댓값은 3^1000 - 2이기 때문이다.

곱할 때마다 %1000000007로 나눠주면서 계산해나가야 한다.

코드

// algorithm study
// SWEA_[D3]7853_오타

#include <iostream>
#include <vector>.

using namespace std;

int main() {
    int test_case;
    cin >> test_case;
    for (int t = 0; t < test_case; t++) {
        string s;
        cin >> s;
        long long answer = 1, chk = 1;
        for (int i = 0; i < s.size(); i++) {
            if (i == 0) {
                if (s[i] == s[i + 1])
                    chk = 1;
                else
                    chk = 2;
            } else if (i == s.size() - 1) {
                if (s[i - 1] == s[i])
                    chk = 1;
                else
                    chk = 2;
            } else {
                if (s[i - 1] == s[i] && s[i] == s[i + 1] && s[i - 1] == s[i + 1])
                    chk = 1;
                else if (s[i - 1] == s[i] || s[i] == s[i + 1] || s[i - 1] == s[i + 1])
                    chk = 2;
                else
                    chk = 3;
            }
            answer *= chk;
            answer %= 1000000007;
        }
        cout << "#" << t + 1 << " " << answer << "\n";
    }
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study