백준 24501 : blobaww (Python)

본문 링크

🔑 코드 1

import sys
input=sys.stdin.readline


N,M=map(int,input().split())
L=[ list(input().rstrip()) for _ in range(N) ]
graph_E=[ [0]*(M+1) for _ in range(N+1) ]
graph_S=[ [0]*(M+1) for _ in range(N+1) ]
graph_M=[ [0]*(M+1) for _ in range(N+1) ]


for i in range(1,N+1):
    for j in range(1,M+1):
        graph_E[i][j] = (graph_E[i - 1][j] + graph_E[i][j - 1] - graph_E[i - 1][j - 1] + 10 ** 9 + 7) % (10 ** 9 + 7)

        if L[i-1][j-1]=="E":
            graph_E[i][j]+=1
            graph_E[i][j]%=10**9+7

for i in range(1,N+1):
    for j in range(1,M+1):
        graph_S[i][j] = (graph_S[i - 1][j] + graph_S[i][j - 1] - graph_S[i - 1][j - 1]+10**9+7)%(10**9+7)
        if L[i-1][j-1]=="S":
            graph_S[i][j]+=graph_E[i][j]
            graph_S[i][j]%=10**9+7
for i in range(1,N+1):
    for j in range(1,M+1):
        graph_M[i][j] = (graph_M[i - 1][j] + graph_M[i][j - 1] - graph_M[i - 1][j - 1]+10**9+7)%(10**9+7)
        if L[i-1][j-1]=="M":
            graph_M[i][j]+=graph_S[i][j]
            graph_M[i][j]%=10**9+7

print(graph_M[N][M]%(10**9+7))

🔑 코드 2

import sys
input=sys.stdin.readline

N,M=map(int,input().split())
graph=[ list(input().rstrip()) for _ in range(N) ]


E_Prefix=[0]*M
S_Prefix=[0]*M
M_Prefix=[0]*M

for i in range(N):
    E_SUM=S_SUM=M_SUM=0
    for j in range(M):
        if graph[i][j]=="E":
            E_SUM+=1
        E_Prefix[j]+=E_SUM

        if graph[i][j]=="S":
            S_SUM+=E_Prefix[j]
        S_Prefix[j]+=S_SUM

        if graph[i][j]=="M":
            M_SUM+=S_Prefix[j]
        M_Prefix[j]+=M_SUM

print(M_Prefix[-1]%(10**9+7))

📌 어떻게 접근할 것인가?

문제에서 원하는것은 $ESM$ 문자열의 경우의 수를 찾는것이다.
다만 주의해야할점은 문자열이 추가될때는 현재 문자에서 아래 또는 오른쪽방향으로만 추가해야한다.
예를들어 (1,1) + (2,2) + (3,3) 으로 문자열이 추가가 될수있지만 (1,1) + (2,2) +(2,1) 이런식으로 문자열이 더해져서는 안된다.

문제에서 다음과 같이 주어졌기 때문이다.
($1 \leq x1 \leq x2 \leq x3 \leq N, 1 \leq y1 \leq y2 \leq y3 \leq M$)

모든 경우의 수를 구해야하기 때문에 코드 1 에서는 2차원 누적합을 통해 문제를 풀었다.

지금 써져있는 문자가 $E$ 라면 현재 칸까지의 $E$ 의 개수에 1을 하나 더하고,
$S$ 라면 현재 칸까지의 $S$ 의 개수에 "$E$ 의 개수"를 더하고,
$M$ 이라면 현재 칸까지의 $M$ 의 개수에 "$S$ 의 개수"를 더해주면 문제에서 요구하는 경우의 수를 구할 수 있다.

📌 코드 1

먼저 $E$ , $S$ , $M$ 의 경우의 수를 담을 2차원 배열을 3개 만들어준다.

이후 리스트 값이 $E$ 일때는 $graphE$ 에 +1을 해준다.
그리고 매번 누적합을 해줘야하는데 2차원 배열에서의 누적합은

graph[i][j]=graph[i-1][j] + graph[i][j-1] - graph[i-1][j-1] 와 같이 더해주어야지
중복된 경우가 생기지 않는다.

또한 문제에서는 경우의 수를 $10^9+7$ 로 나눈 나머지를 구해야한다.

이때 중요한것은 graph[i-1][j] + graph[i][j-1] - graph[i-1][j-1] 연산을 하는 도중에
배열에 들어있는 값은 나머지 값이기 때문에 graph[i-1][j] 가 graph[i-1][j-1] 보다 작을 수 있다. 따라서 음수가 나올수 있으므로

(graph_E[i - 1][j] + graph_E[i][j - 1] - graph_E[i - 1][j - 1] + 10 ** 9 + 7) % (10 ** 9 + 7) 와 같이 처리를 해줘야한다.

다음으로 $S$ 인 경우에는 그대로 누적합을 해주지만 리스트 값이 $S$ 일때
+1 을 해주는것이 아니라 E의 개수를 더해주어야한다.

$M$ 도 똑같이 반복해주면 $graphM$에는 결국 $E$ ,$S$ ,$M$ 모두 조건을 만족하는 문자열의 경우의 수가 나타나게된다.

📌 코드 2

이번에는 $E$ , $S$ , $M$ 에 대한 1차원 누적합 배열을 만들어주었다.
이중반복문을 통해서 매번 E_SUM=S_SUM=M_SUM=0 값을 초기화 해주고 이 값들은 현재까지 나온 문자의 개수를 의미한다.

이후 누적합 배열에 매번 현재까지의 $E$, $S$ , $M$ 의 개수를 더해준다.
이때 중요한것은 S_SUM 과 M_SUM 은 1을 더하는것이 아니라 현재까지 E,S의 누적합 개수를 더해주어야한다는 점이다.