방구석프로의 이야기

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

문제 해결을 위한 과정

이 문제의 경우 dp를 이용하면 쉽게 해결할 수 있었습니다. 문제에서 볼 수 있듯 어떤 칸에 대해서 위, 왼쪽, 좌측대각선 위(11시 방향) 중 최댓값을 현재 칸에 더해주고, 이 결과로 나온 배열에서 제일 우측 하단 배열의 값을 출력해 주면 됩니다. 다만 0번째 행, 0번째 열 처럼 위, 왼쪽, 좌측 대각선 중 한 경우라도 없는 경우는 따로 예외처리를 하여 해결하면 됩니다. 

소스코드

n, m = map(int, input().split())
graph = []
for _ in range(n):
  graph.append(list(map(int, input().split())))

for i in range(n):
  for j in range(m):
    if i == 0:
      if j != 0:
        graph[i][j] += graph[i][j-1]
    else:
      if j == 0:
        graph[i][j] += graph[i-1][j]
      else:
        graph[i][j] += max(graph[i-1][j], graph[i][j-1], graph[i-1][j-1])

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