백준 #31828 MR.DR 문자열

문제 링크

[31828 MR.DR 문자열]

문제 설명

길이가 4이상인 영어 대문자로 이루어진 서로 다른 모든 문자열에 대하여 0개 이상의 문자를 제거 했을 때 MRDR을 남길 수 있는 문자열의 개수를 구하는 문제

코드

import sys
input = sys.stdin.readline


N = int(input())
MOD = int(1e9 + 7)
dp = [[0] * 5 for _ in range(N + 1)]

dp[0][0] = 1

for i in range(1, N + 1):
    for j in range(5):
        if j == 0:
            dp[i][j] = dp[i - 1][j] * 26
        else:
            dp[i][j] += dp[i - 1][j] * 25
            dp[i][j] += dp[i - 1][j - 1]
        dp[i][j] %= MOD


print(dp[N][4])

풀이

처음에 조합으로 시도하다가 중복처리가 까다로운것 같아서 DP로 풀이했다. 2차원 배열을 만든 후에 $dp[i][j]$를 길이가 i인 문자열 중 MRDR의 j번째까지 포함하는 문자열의 개수로 정의하였다. $j=0$인 경우에는 이전 길이의 문자열에서 어떤 문자가 와도 상관 없기 때문에 이전 단계에서 26을 곱해주면 된다.

\[dp[i][0]=dp[i-1][0]*26\]

$j\neq0$인 경우에는 이전 길이의 문자열에서 이미 $j$번까지 포함한 경우에는 $j$번 문자가 포함되면 안되기 때문에 25를 곱해주고

\[dp[i][j] += dp[i - 1][j] * 25\]

$j-1$번까지 포함한 경우에는 $j$번째 올 문자가 확정되기 때문에 그냥 이전 길이의 문자열 개수를 더해주면 된다.

\[dp[i][j] += dp[i - 1][j - 1]\]

계속 틀려서 어디서 틀린지 찾고있었는데 1e9 이부분을 10e9로 잘 못써가지구..ㅜㅜ 참고로 10e9는 0이 9개가 아니라 10개! 10에다가 e9를 곱한거라고 생각하면된다. 1e9는 1에다 e9를 곱했으니 0이 9개이구.. 오랜만에 쓰다보니깐 이런것도 헷갈리는구나 라고 생각하게된 문제였다…!!