문제

https://www.acmicpc.net/problem/2169

소스코드

if __name__ == "__main__":  
    n,m = map(int,input().split())
    dp = [list(map(int,input().split())) for _ in range(n)]

    for i in range(1,m):
        dp[0][i] += dp[0][i-1]
    
    for i in range(1,n):
        left = dp[i][:]
        right = dp[i][:]

        for j in range(m):
            if j == 0:
                left[j] += dp[i-1][j]
            else:
                left[j] += max(dp[i-1][j],left[j-1])
        for j in range(m-1,-1,-1):
            if j == m-1:
                right[j] += dp[i-1][j]
            else:
                right[j] += max(dp[i-1][j],right[j+1])
        for j in range(m):
            dp[i][j] = max(left[j],right[j])
    print(dp[n-1][m-1])

설명

탐색하는 방법은 위에서 오는 경우, 왼쪽에서 오는 경우, 오른쪽에서 오는 경우이다. 이때 어디서 오는 값이 최대값인지 탐색해야한다.

1. 첫번째 행은 왼 -> 오 로 가는 방향만 (N,M)으로 가면서 최대값을 가지는 방법이다.
2. 1 ~ N-1 행까지는 (왼 ->오),(오 -> 왼)인 2가지 경우가 존재한다.
   2-1). (왼 -> 오) 인 경우는 위에서 내려오는 경우와 왼쪽에서 오는 경우를 비교해서 최대값을 메모이제이션 해준다. 이때 1열은 무조건 위에서 내려오는 값이 최대값이다.
   2-2). (오 -> 왼) 인 경우는 위에서 내려오는 경우와 오른쪽에서 오는 경우를 비교해서 최대값을 메모이제이션 해준다. 이때 M-1 열은 무조건 위에서 내려오는 값이 최대값이다.

3.한 행씩 왼>오/오>왼을 비교해서 임시배열에 넣어주고 각 임시배열을 순차적으로 비교해서 최대갮을 DP[i][j]에 넣어준다.

후기

처음에 방문했던 곳은 다시 재방문하지 않는다와 2차원 배열 탐색만 보고 BFS + Visited 체크해서 푸는 완전탐색으로 접근하고 문제를 풀었다 당연히 시간초과 ;;;
이럴 때 혹시 ~ 하면서 pypy3로 돌려보면 메모리 초과가 난다 ; ㅋ

재방문 하지 않는다의 뜻은 왼쪽에서 왔을 때 다시 왼쪽을 탐색하지 말라는 뜻인데 그걸 몰랐다.

어디까지 탐색하고 그 다음을 탐색할 때 값이 정해지고 특정 부분부터 새로운 탐색이 시작되면 특정 부분 이전은 고정이니까 메모이제이션을 통해서 저장해야겠다. 라는 생각을 해야한다.

또 완전탐색인가? 시간초과 나겠다 그러면 DP이다. DP면 규칙이 있을 것이다. 라는 생각을 가지고 문제에 접근하자

참조

https://wooono.tistory.com/605