백준 11048 : 이동하기 - 파이썬 Python

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

11048번: 이동하기

 

생각하기

가져올 수 있는 사탕의 최대를 구하는 것이기 때문에 생각을 했다

• DFS로 모든 경우를 다 해봐?
• 규칙 같은 것을 찾아서 DP로 만들어볼까?

DFS로 풀면 시간초과가 발생할 것 같다는 생각이 들었다. 

1000 * 1000 인데 각 경우가 3가지 경우만 고려하더라도 

각 칸은 세가지의 경우로 뻗어나갈 가지수를 가지고 있으므로 최대 가로 세로 1000칸이라면 

3000000의 가지수가 나오고 300000 * 1000 * 1000 -> 1억을 넘어버린다.

 

DP로 풀자고 생각이 들었다. 

점화식을 만들어야 하는데 이전의 결과가 현재에 영향을 어떻게 주는지 생각해야 했다.

만약 이전에 있던 칸이 최대의 사탕 개수를 가지고 있던 칸이고 현재 칸에 왔다면

 -> 그것이 곧 가장 많은 개수의 사탕을 가지게 된다

 

즉, 현재 칸으로 올 수 있는 세가지 가짓수 중 최대가 현재로! 

 

메모리는?

배열이 1000칸인 경우 4byte * 1000 = 4000byte = 3.7KB -> 넉넉하다

 

 

구현하기

초기값들로 1열과 1행을 모두 구해놓고

각 칸은 가질 수 있는 3칸의 최대값을 저장해놓는 방식으로 dp 메모이제이션 테이블을 구성한다

 

dp 테이블은 각각의 칸에서 가져올 수 있는 사탕의 최대값이다

dp[i-1][j] + data[i][j],

 

dp[i][j-1]+data[i][j]

 

dp[i-1][j-1]+data[i][j]

 

위의 세 경우의 중 가장 max인 것을 dp[i][j] (i,j칸에서 가져올 수 있는 사탕의 최대값) 을 저장한다

 

 

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

data = []
dp = [[0 for c in range(M)]for r in range(N)]
for i in range(N):
    data.append(list(map(int, input().split())))

tmp_sum1 = 0
for j in range(M):
    tmp_sum1 += data[0][j]
    dp[0][j] = tmp_sum1

tmp_sum2 = 0
for i in range(N):
    tmp_sum2 += data[i][0]
    dp[i][0] = tmp_sum2

for i in range(1, N):
    for j in range(1, M):
        # max_num = max(dp[i-1][j] + data[i][j], dp[i][j-1]+data[i][j])
        # max_num_result = max(max_num, dp[i-1][j-1]+data[i][j])
        # dp[i][j] = max_num_result
        dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + data[i][j]


print(dp[N-1][M-1])