백준|11048번|이동하기

문제설명
M*N 크기의 미로가 있고 그 미로의 각 칸마다 사탕이 놓여있을 때 N,M까지 이동했을 때 가질 수 있는 최대의 사탕 개수를 출력하는 문제입니다. 이동을 할때는 N+1번째칸, M+1번째칸 또는 (N+1,M+1)번칸으로만 이동이 가능합니다.

작동 순서
1. 미로의 크기를 입력받습니다.
2. (N+1,M+1)로는 이동을 할 필요가 없으므로 N-1번째 칸과 M-1번째 칸들을 비교합니다.
3. 가능한 칸들중 사탕의 개수가 더 많은 칸의 개수를 가져와서 현재 칸에 더해줍니다.
4. N,M번째까지 탐색 완료 후 N,M번째 칸의 개수를 출력합니다.

소스코드

import sys
N, M = map(int, sys.stdin.readline().split())
maze = []

for h in range(N):
    maze.append(list(map(int, sys.stdin.readline().split())))
    for v in range(M):
        if h == 0 and v == 0:
            pass
        elif h-1 >= 0:
            if v-1 >= 0:
                maze[h][v] += max(maze[h-1][v], maze[h][v-1])
            else:
                maze[h][v] += maze[h-1][v]
        else:
            maze[h][v] += maze[h][v-1]

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

후기
처음에 브루트포스로 풀었었는데 시간초과가 나길래 보니 DP로 푸는 문제였습니다. 아직도 문제 이해력이나 해결 능력이 많이 부족한 것 같습니다.