[백준 21923번] 곡예 비행 (python)

문제

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

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

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

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

<그림 2> 모형 비행기의 이동 경로

위의 예시에서, 각 칸에 적힌 수는 그 칸에 부여된 점수이고, 수가 적혀 있지 않은 칸의 점수는 0이라고 가정하자. 그리고 모형 비행기가 1, 2, ..., 15의 순서대로 비행을 했다고 가정하자.

<그림 3> 상승 비행의 이동 경로

<그림 4> 하강 비행의 이동 경로

이 경우, 상승 비행은 1이 적힌 칸에서 시작하고 8이 적힌 칸에서 끝난다. 하강 비행은 8이 적힌 칸에서 시작하고 15가 적힌 칸에서 끝난다. 이와 같이 비행을 하였을 때 얻는 점수는 (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8) + (8 + 9 + 10 + 11 + 12 + 13 + 14 + 15) = 128 이다.

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

 

기록

(dp 16일차) dp 제발 그만.. 그래도 많이 발전한 것 같아 뿌듯하다!

 

이번 문제는 n*m의 이차원 dp 배열 두 개를 사용해 출발지부터 (i, j)까지 상승비행한 점수+ (i, j)부터 목적지까지 하강비행한 점수를 계산하는 방법으로 풀었다. 따라서 dp_up[i][j]에는 출발지부터 (i, j)까지 상승비행한 최대점수를, dp_down[i][j]에는 (i, j)부터 목적지까지 하강비행하는 최대점수를 저장했다. 최대점수 구하는 방법은 상승비행의 경우 출발지부터 시작해서 현재 칸의 아래와 왼쪽에서 오는 방법 중 더 큰 비행점수를 저장했고, 하강비행의 경우 목적지부터 현재칸의 아래와 오른쪽에서 오는 방법 중 더 큰 비행점수를 저장했다.

 

코드

n, m = map(int, input().split())
board = [list(map(int, input().split())) for i in range(n)]

dp_up = [[-1e9]*m for i in range(n)]
dp_down = [[-1e9]*m for i in range(n)]
dp_up[n-1][0] = board[n-1][0]
dp_down[n-1][m-1] = board[n-1][m-1]

for i in range(n-1, -1, -1):
    for j in range(m):
        if i==n-1 and j==0 : continue
        if i<n-1 : dp_up[i][j] = max(dp_up[i][j], dp_up[i+1][j])
        if j>0 : dp_up[i][j] = max(dp_up[i][j], dp_up[i][j-1])
        dp_up[i][j]+=board[i][j]

for i in range(n-1, -1, -1):
    for j in range(m-1, -1, -1):
        if i==n-1 and j==m-1 : continue
        if i<n-1 : dp_down[i][j] = max(dp_down[i][j], dp_down[i+1][j])
        if j<m-1 : dp_down[i][j] = max(dp_down[i][j], dp_down[i][j+1])
        dp_down[i][j]+=board[i][j]

_max = -1e9
for i in range(n):
    for j in range(m):
        _max = max(_max, dp_up[i][j]+dp_down[i][j])
print(_max)

1. 출발지부터 모든 칸까지의 상승비행 최대점수를 저장할 dp_up, 모든 칸부터 목적지까지의 하강비행 최대점수를 저장할 dp_down 배열을 생성한다. dp_up에 출발지 점수를, dp_down에 목적지 점수를 초기화한다.

2. dp_up을 채워넣는다. 출발지부터 오른쪽->위로 dp_up[i+1][j-1]와 dp_up[i][j-1] 중 큰 값에 현재 칸 점수를 더해 저장한다.

3. dp_down을 채워넣는다. 목적지부터 왼쪽->위로 dp_up[i+1][j-1]와 dp_up[i][j+1] 중 큰 값에 현재 칸 점수를 더해 저장한다.

4. 두 배열을 더하면 출발지부터 (i, j)까지 상승비행한 점수+ (i, j)부터 목적지까지 하강비행한 점수가 된다. 따라서 배열의 모든 칸을 더해 가장 큰 값을 출력한다.