백준 11048 이동하기

문제풀이

(r, c)까지 왔을 때 가질 수 있는 사탕의 최댓값을 dp[r][c]이라 하면, 점화식은 다음과 같이 쓸 수 있다.

dp[r][c] = max(dp[r][c-1], dp[r-1][c]

즉, (r,c) 까지 오는 방법은 같은 행의 왼쪽 열에서 오거나, 이전 행의 같은 열에서 오는 두가지 방법이 있다. 

따라서 모든 r을 0부터 n까지 반복한 후, dp[n][m]을 반환하면 된다.

 

Python Code

import sys
n,m = map(int,sys.stdin.readline().split())
dp = list(map(int,sys.stdin.readline().split()))
for j in range(1,m):
    dp[j] = dp[j-1]+dp[j]
for i in range(1,n):
    maze = list(map(int,sys.stdin.readline().split()))
    dp[0]+=maze[0]
    for j in range(1,m):
        dp[j] = max(dp[j-1]+maze[j],dp[j]+maze[j])
print(dp[-1])

Line 4 : 첫번째 행에 대한 연산이다.

Line 6 : 두번째 행 이후에 대한 연산이다.

 

비효율적이었던 풀이

 풀이 설명을 보면 dp가 n*m 인 행렬이지만, 위의 코드는 길이가 m인 배열이다. 처음에는 maze 행렬을 모두 받아서 가진 상황에서 풀이를 했는데, 시간이 다른 풀이들에 비해 오래걸렸다. 좀 더 효율적으로 수정한 코드가 위의 코드이며, maze를 한줄씩 받으며 즉시 처리하는 식으로 바꿨더니 시간이 1632ms에서 720ms로 절반이상 줄었다. 메모리 역시 절반 이상 줄일 수 있었다.

 아래는 첫 풀이이다. 위의 코드와는 달리 bfs를 이용하여 0,0 부터 m,n까지 dp 행렬을 채워나갔으며, 위에서 말했듯, maze를 모두 받고 시작했고, dp는 모든 요소가 0인 m*n 행렬로 초기화하였다.

import collections
import sys
 
def summation(maze):
    ans = 0
    for m in maze:
        ans += sum(m)
    return ans 
 
n,m = map(int,sys.stdin.readline().split())
maze = []
for i in range(n):
    maze.append(list(map(int,sys.stdin.readline().split())))
 
 
if n < 2 or m < 2:
    print(summation(maze))
else:
    dp = [[0 for i in range(m)] for j in range(n)]
    dp[0][0]=maze[0][0]
    q = collections.deque()
    q.append([1,0])
    q.append([0,1])
    while q:
        row,col = q.popleft()
        if col == 0 : dp[row][col]=dp[row-1][col]+maze[row][col]
        elif row == 0 : dp[row][col]=dp[row][col-1]+maze[row][col]
        else : dp[row][col] = max(dp[row-1][col]+maze[row][col], dp[row][col-1]+maze[row][col])
 
        if row == n and col == m : break
        if col == 0 and row < n-1 :
            q.append([row+1,col])
        if col < m-1 :
            q.append([row,col+1])
    print(dp[-1][-1])

 

 

문제 링크

11048번: 이동하기