백준 파이썬 11048 이동하기

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

11048번: 이동하기

 

 

 

DP문제인건 알았는데 어떻게 처리해야 할지 오랜만에 풀다보니 감이 안왔었는데

 

초반에는 BFS식으로 풀었다가 시간초과가 발생했습니다.

 

from collections import deque

n,m = map(int,input().split())
s = []
dp = [[0]*(m+1) for _ in range(n+1)]

plan = [[0,1],[1,0],[1,1]]

for i in range(n):
    s.append(list(map(int,input().split())))

queue = deque([])
queue.append([0,0])
dp[0][0] = s[0][0]

while queue:
    x,y = queue.popleft()

    for i in range(3):
        nx = plan[i][0] + x
        ny = plan[i][1] + y

        if 0 <= nx < n and 0 <= ny < m:
            dp[nx][ny] = max(dp[nx][ny], dp[x][y] + s[nx][ny])
            queue.append([nx,ny])


print(dp[n-1][m-1])

지금은 조금 코드가 바뀌어서 안될지도모르겠는데

대충 이런 느낌으로 BFS를 짰는데 시간초과가 났고 조금 해당 로직이 이중FOR문보다 약 5배 이상 더 효율이 안좋다

라는걸 알게 되었습니다.

 

가능하면 FOR문 안에서 끝낼수 있도록 DP를 설계를 하였고 성공하였습니다.

 

 

내가 지금 위치한 S수열의 숫자와 이전까지 쌓아온 DP의 유효값 (n-1)(m) (n)(m-1) (n-1)(m-1) 중 가장 높은 값을 입력

n,m = map(int,input().split())
s = []
dp = [[0]*(m+1) for _ in range(n+1)]

for i in range(n):
    s.append(list(map(int,input().split())))

for i in range(1,n+1):
    for j in range(1,m+1):
        dp[i][j] = s[i-1][j-1] + max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

print(dp[n][m])

성공~

 

요즘 알고리즘을 안하다보니 시간이 꽤 오래걸렸다.