| 시간 제한 | 메모리 제한 |
| 1초 | 1024MB |
문제
길이가 4 이상인 영어 대문자로만 이루어질 수 있는 서로 다른 모든 문자열에 대해, 0개 이상의 문자를 제거하였을 때 문자열 MRDR이 되는 문자열을 MR.DR 문자열이라고 한다.
정수 N이 주어질 때, 길이가 N인 MR.DR 문자열의 개수를 구하는 프로그램을 작성하라.
입력
첫 번째 줄에 정수 N이 주어진다. ( 4 ≤ N ≤ 100,000)
출력
길이가 N인 MR.DR 문자열의 개수를 출력하라.
이때 정답이 매우 커질 수 있으므로 정답을 1,000,000,007 (=109 + 7)로 나눈 나머지를 출력하라.
풀이
시간 제한이 1초, N의 범위가 100,000까지인 것으로 보아 최소한 O(NlogN)으로 끝내야 한다. 근데 이분탐색 요소는 없으니 O(N)일 것 같다는 생각으로 출발. 1e9+7 모듈러까지 있다? 아, 그럼 선형 DP겠네요?
(1) 잘못된 접근
"M", "R", "D", "R"이 연속되지 않더라도 순서대로만 들어있으면 되는 문제. 일단 N = 4일 때 "MRDR"로 1가지 경우만 가능하고 N = 5일 때에는 "_M_R_D_R_"의 언더바 자리에 아무 알파벳이나 끼워넣는 모든 경우가 가능하다. 다만, "MM_R_D_R_"과 "_MMR_D_R_"은 모두 "MMRDR"로 표현되어 같은 경우이기 때문에 "전체 문자열의 길이 - 1"만큼의 경우를 중복으로 제거해줘야 한다. 나는 점화식을 다음과 같이 세웠다.
dp[i] = (dp[i - 1] * 26 * i - i + 1) % 1_000_000_007
뭔가 그럴듯 하고 될 것 같지만 이 풀이가 일으키는 오류는 이렇다.
MRDR이 완성된 상태로 확인하지만 N = 8부터는 MRDR이 2개 이상 만들어질 수 있다. 위의 상황을 보면 "MRDRMRDA"와 "MRDMRDRA"라는 서로 다른 두 문자열에서 R을 끼워넣어 MRDR을 완성하지만 두 가지 경우가 같은 결과를 낳아 중복된다. 이걸 어떻게 걸러낼까?
(2) 정해
다시 접근해보자. 길이 i의 문자열 Si를 만든다. Si는 Si-1에서 하나의 문자를 끼워넣어서도 만들 수 있지만 존재하는 모든 경우에서 Si-1의 맨 끝에 새 문자를 추가하는 것으로도 Si를 구성할 수 있다. 그러니까 이미 만들어진 i-1개의 문자들 사이의 i개의 공간 중 1개를 택해 문자를 끼워넣는 건 하나의 문자로 파생되는 경우의 수가 너무 많다는 것이다. 이것 때문에 중복이 발생하니, i-1개의 문자를 그대로 두고 맨 끝에 하나를 덧붙이면 한 가지 경우에서 한 가지 경우만 파생된다.
이제 dp테이블을 2차원으로 선언해보자. dp[i][j] = "MRDR"중 i번째 글자까지 완성된 j길이의 문자열의 경우의 수다. N이 주어지면 dp테이블의 크기는 dp = [[0] * (N+1) for _ in range(5)]로 선언하면 된다.
dp테이블의 관리는 이런식으로 이뤄진다.
이젠 점화식을 다시 세워보자.
dp[0][i] = dp[0][i - 1] * 26
dp[i][j] = dp[i][j] + dp[i][j - 1] * 25 (i번째까지 완성된 문자열은 MRDR의 i+1번째 알파벳을 제외한 25개 가능)
dp[i][j] = dp[i][j] + dp[i - 1][j - 1] (i - 1번째까지 완성된 문자열로 i번째까지 완성하려면 1개의 알파벳만 가능)
정답 코드
def solution():
N = int(input())
mod = int(1e9 + 7)
dp = [[0] * (N + 1) for _ in range(5)]
dp[0][0] = 1
for j in range(1, N + 1):
dp[0][j] = dp[0][j - 1] * 26 % mod
for i in range(1, 5):
dp[i][j] += dp[i][j - 1] * 25
dp[i][j] += dp[i - 1][j - 1]
dp[i][j] %= mod
print(dp[4][N])
solution()
