[boj 24501] blobaww

문제 링크

 

문제를 풀고 나서 다른 분들의 풀이를 봤더니, 누적합이라는 방법으로 풀었더라구요... 저는 생각도 못했습니다...

 

저는 dp로 접근하면서 각 부분에서 유효한 경로가 몇개인지 세는 방식으로 접근했습니다.

 

import sys
input = sys.stdin.readline


MOD = 1_000_000_007


def solve():
    N, M = map(int, input().split())
    
    maps = [list(input().rstrip()) for _ in range(N)]
    
    dp = [[[0]*3 for _ in range(M+1)] for _ in range(N+1)]
    
    for i in range(1, N+1):
        for j in range(1, M+1):
            dp[i][j][0] = dp[i][j-1][0] + dp[i-1][j][0] - dp[i-1][j-1][0]
            dp[i][j][1] = dp[i][j-1][1] + dp[i-1][j][1] - dp[i-1][j-1][1]
            dp[i][j][2] = dp[i][j-1][2] + dp[i-1][j][2] - dp[i-1][j-1][2]
            
            if maps[i-1][j-1] == "E":
                dp[i][j][0] += 1
            elif maps[i-1][j-1] == "S":
                dp[i][j][1] += dp[i][j-1][0] + dp[i-1][j][0] - dp[i-1][j-1][0]
            else:
                dp[i][j][2] += dp[i][j-1][1] + dp[i-1][j][1] - dp[i-1][j-1][1]

            dp[i][j][0] %= MOD
            dp[i][j][1] %= MOD
            dp[i][j][2] %= MOD
                
    
    print(dp[-1][-1][-1])
    
    return


def main():
    solve()
    
    return


if __name__ == "__main__":
    main()