테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== a^ib^jc^k ======

===== 풀이 =====
  * 거의 비슷한 문제를 많이 봤던것 같은 느낌의 DP.
  * dp_a[i], dp_b[i], dp_c[i] 를 S[:i+1]안에 포함된 $a^i$, $a^ib^j$, $a^ib^jc^k$ 의 갯수라고 각각 정의하자
  * S[i]=='a' 라면 S[:i+1]에 있는 $a^i$들은 S[:i]안에 있었던 $a^i$들 + S[:i]안에 있었던 $a^i$ 에 s[i]를 뒤에 붙인 것 + 그냥 s[i] 한글자로 이루어진것, 이렇게 해서 dp_a[i] = dp_a[i-1]*2+1 이 된다.
  * S[i]=='b' 라면 S[:i+1]에 있는 $b^i$들은 S[:i]안에 있었던 $b^i$들 + S[:i]안에 있었던 $b^i$ 에 s[i]를 뒤에 붙인 것 + S[:i]안에 있었던 $a^i$ 뒤에 s[i]를 붙인것, 이렇게 해서 dp_b[i] = dp_b[i-1]*2+dp_a[i-1] 이 된다.
  * S[i]=='c'일때도 'b'일때봐 비슷하게 dp_c[i]를 구한다.
  * dp테이블 한칸을 채우는데에 O(1)이므로 총 시간복잡도는 O(n)

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 15485. \(a^ib^jc^k\)".

- Problem link: https://www.acmicpc.net/problem/15485
- Solution link: http://www.teferi.net/ps/problems/boj/15485
"""

MOD = 1_000_000_007


def main():
    S = input()

    count_a = count_b = count_c = 0
    for c in S:
        if c == 'a':
            count_a = (count_a * 2 + 1) % MOD
        elif c == 'b':
            count_b = (count_b * 2 + count_a) % MOD
        elif c == 'c':
            count_c = (count_c * 2 + count_b) % MOD

    print(count_c)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_2}}