[Python] BOJ 백준 21923 곡예 비행

문제

동헌이는 모형 비행기 조종 대회에 참가하였다. 이 대회에서는 격자 모양의 공간에서 모형 비행기를 조종하여 얻는 비행 점수로 순위를 매긴다. 격자의 각 칸에는 점수가 부여되어 있고, 비행 점수는 "상승 비행을 할 때 지나간 칸에 부여된 점수의 총합"과 "하강 비행을 할 때 지나간 칸에 부여된 점수의 총합"을 더한 값이다. 출발한 칸과 도착한 칸도 지나간 칸으로 간주한다.

<그림 1> 시작과 끝 칸 및 가능한 이동 방향

모형 비행기는 맨 왼쪽 아래 칸에서 상승 비행으로 비행을 시작해야 하고, 중간에 상승 비행에서 하강 비행으로 변경한 후, 맨 오른쪽 아래 칸에서 하강 비행으로 비행을 종료해야 한다. 상승 비행에서 하강 비행으로 변경할 때에는 다른 칸으로 이동할 수 없다. 즉, 상승 비행이 끝난 칸에서 하강 비행을 시작해야 한다.

모형 비행기는 상승 비행 중에는 앞 또는 위로만 이동할 수 있고, 하강 비행 중에는 앞 또는 아래로만 이동할 수 있다.

동헌이는 이 대회에서 얻을 수 있는 최대 비행 점수가 궁금하다. 동헌이를 위해 얻을 수 있는 최대 비행 점수를 구해주자.

풀이

꽤나 까다로운 dp 문제였던 것 같다. 우선 상승 비행과 하강 비행으로 나누어 두 번 진행해야 한다는 번거로움이 있었다.

테이블을 두 개를 만들어 행렬 덧셈으로 답을 도출하려고 했는데, 이런 저런 예외처리를 하느라 꽤 고생했다.

상승 비행과 하강 비행의 테이블을 zip을 이용해서 행렬 덧셈을 해주고, 나온 최대 값이 얻을 수 있는 최대 점수가 된다.

import sys

si = sys.stdin.readline
n, m = map(int, si().split())
graph = [list(map(int, si().split())) for _ in range(n)]
go_up = [[-sys.maxsize] * m for _ in range(n)]
go_down = [[-sys.maxsize] * m for _ in range(n)]


def flight():
    sx, sy = n - 1, 0
    ex, ey = n - 1, m - 1
    up = [(1, 0), (0, -1)]
    down = [(1, 0), (0, 1)]
    go_up[sx][sy] = graph[sx][sy]
    go_down[ex][ey] = graph[ex][ey]
    for r in range(sx, -1, -1):
        for c in range(0, m):
            for nx, ny in up:
                tx, ty = r + nx, c + ny
                if 0 <= tx < n and 0 <= ty < m:
                    go_up[r][c] = max(go_up[r][c], graph[r][c] + go_up[tx][ty])
    for r in range(ex, -1, -1):
        for c in range(ey, -1, -1):
            for nx, ny in down:
                tx, ty = r + nx, c + ny
                if 0 <= tx < n and 0 <= ty < m:
                    go_down[r][c] = max(go_down[r][c], go_down[tx][ty] + graph[r][c])

    ans = [[c + d for c, d in zip(a, b)] for a, b in zip(go_down, go_up)]
    _max = -sys.maxsize
    for i in ans:
        if max(i) > _max:
            _max = max(i)
    return _max


answer = flight()
print(answer)