【경쟁 프로 전형적인 90문】008의 해설(python)

개요

경쟁 프로 전형 90문 의 해설 기사입니다.
해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다.

※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다.
※★5이상의 문제는 난이도적으로 후회하고 있기 때문에, 투고 시기가 늦어질 가능성이 있습니다. (대신 정중하게 해설 해 주시는 분이라면 꼭 부탁드립니다)

이슈008-AtCounter

문제 개요

문자열 S로부터 임의의 문자를 순서를 바꾸지 않고 꺼냈을 때에, "atcoder"(이하, 문자열 T라고 합니다.)가 되는 개수를 구한다.

해결 방법

우선, 간단하게 S로부터 "atcoder"의 문자를 각각 검색하는 방법이 생각됩니다만,
이 생각으로는 문자열의 길이 N을 7회(T의 길이분) 검색하기 때문에 $N^7$가 되어 TLE가 되어 버립니다.

그래서 이번에는 DP(동적 계획법)를 이용합니다.
dp[i][j]를, S의 i문자째까지를 이용했을 때, T의 j문자째까지를 만드는 거리의 수로 정의합니다.
그러면
1. $S[i] = T[j]$일 때(S의 i문자목과 T의 j문자목이 같을 때)

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

※S의 i 문자목을 사용해 T의 j문자로 할 때와, S의 i문자를 사용하지 않고 j문자목까지 만들었을 때의 합입니다.

2. $S[i] ≠ T[j]$일 때(S의 i문자목과 T의 j문자목이 같지 않을 때)

$dp[i][j] = dp[i-1][j]$

※S의 i-1 문자째까지를 사용해 T의 j문자를 만드는 대로 수와 같습니다.

의 2개의 점화식이 요구됩니다.
또, j=0일 때는, 문자를 꺼내지 않는 방법, 즉 1대로로 할 수 있으므로,

$dp[i][0] = 1$

i=0일 때(그리고 j≠0) 때는, S를 1문자도 사용하지 않고, T의 j문자까지 만들 수 없기 때문에,

$dp[0][j] = 0$

라고 생각됩니다. 여기까지 요구되면, i, j를 작은 순서로 계산함으로써,
모든 i, j에 대해 dp를 구할 수 있고, dp[N][7]이 대답이 됩니다.



인용 소스 : 경쟁 프로 전형 90문 Github

구현

answer.py

# 入力の受け取り

N = int(input())
S = input()

# 今回はatcoderをTとする
T = "atcoder"

# 余りのための変数
mod = 10**9+7

#0文字からN文字まで考えるので、"+1個"配列を定義
dp = [[0]*(len(T)+1) for _ in range(N+1)]

# j=0の時、全て1を代入
for i in range(N+1):
  dp[i][0] = 1

# S[i]がT[j]に等しいかで場合分け
# dpのiとS[i]で示すiが1ズレている点に注意（jも同様）
# 答えをmodで割った余りを格納
for i in range(N):
  for j in range(len(T)):
    if S[i] == T[j]:
      dp[i+1][j+1] = dp[i][j] + dp[i][j+1]
      dp[i+1][j+1] %= mod
    else:
      dp[i+1][j+1] = dp[i][j+1]
      dp[i+1][j+1] %= mod

# N文字まで使って、Tになる時の通り数を出力
print(dp[N][len(T)])

마지막으로

문제의 해설을 읽어도 다른 사람의 코드를 봐도 확실히 모르는 분
힘에 조금이라도 될 수 있으면 다행입니다.
코드의 개선점이나 그 외, 의견등 있으면, 부담없이 코멘트해 주세요.
또, 이 기사를 읽고 이해할 수 있었던 분은 꼭 LGTM를 눌러 주실 수 있으면 기쁩니다.
(기사 투고의 모티베가 됩니다.)

여기까지 읽어 주셔서 감사합니다.