15485. ＼（a＾ib＾jc＾k＼）

업데이트 시간 : 2023-04-05 10:42:25 +0000

[Gold II] (a^ib^jc^k) - 15485

문제 링크

성능 요약

메모리: 141392 KB, 시간: 180 ms

분류

다이나믹 프로그래밍

문제 설명

a, b, c로만 이루어진 문자열 S가 주어졌을 때, S의 부분 수열 중에서 aⁱb^jc^k의 형태로 이루어진 것의 개수를 구하는 프로그램을 작성하시오. 이때, i ≥ 1, j ≥ 1, k ≥ 1을 만족해야 한다.

aⁱb^jc^k는 a가 i개 나오고, 이어서 b가 j개, c가 k개 연속해서 나오는 문자열이다. 예를 들어, a²b³c¹은 "aabbbc"를 나타내며, a³b¹c⁶은 "aaabcccccc"를 나타낸다.

입력

첫째 줄에 a, b, c로만 이루어진 문자열 S가 주어진다. S의 길이는 1,000,000을 넘지 않는다.

출력

첫째 줄에 S의 부분 수열 중에서 aⁱb^jc^k 형태로 이루어진 것의 개수를 1,000,000,007로 나눈 나머지를 출력한다.

💡 Solutions

📄 ＼（a＾ib＾jc＾k＼）.py

import sys
lst = sys.stdin.readline().rstrip()

len_lst = len(lst)
matrix = [[0 for _ in range(len_lst)] for _ in range(3)]
K = 1000000007
cnt_a = 0
cnt_b = 0
cnt_c = 0
for c in range(len_lst):
    if lst[c] == 'a':
        matrix[0][c] = (matrix[0][c-1] * 2 %K + 1)%K
        matrix[1][c] = matrix[1][c-1]
        matrix[2][c] = matrix[2][c-1]
    elif lst[c] == 'b':
        matrix[0][c] = matrix[0][c-1]
        matrix[1][c] = (matrix[0][c-1]+(matrix[1][c-1] * 2 %K))%K # 조합 nCr = n-1Cr + nCr-1 같은 느낌이네
        matrix[2][c] = matrix[2][c-1]
    elif lst[c] == 'c':
        matrix[0][c] = matrix[0][c-1]
        matrix[1][c] = matrix[1][c-1]
        matrix[2][c] = (matrix[1][c-1]+(matrix[2][c-1] * 2 %K)%K)%K

print(matrix[-1][-1])