[Python/파이썬] 백준 21923번 곡예 비행

21923번: 곡예 비행

 

코드

n, m = map(int, input().split())
scores = [[0]+list(map(int, input().split())) for _ in range(n)]

up = [[-int(1e9)]*(m+1) for _ in range(n+1)]    # 상승 비행 점수
down = [[-int(1e9)]*(m+1) for _ in range(n+1)]  # 하강 비행 점수
up[n-1][1] = scores[n-1][1]  # 출발점

# 상승
for j in range(1, m+1):
    for i in range(n-1, -1, -1):
        if i == n-1:    # 바닥
            if j == 1:
                continue
            up[i][j] = up[i][j-1]    # 앞
        else:
            up[i][j] = max(up[i][j-1], up[i+1][j])    # 앞, 위
        up[i][j] += scores[i][j]
# 하강
for j in range(1, m+1):
    for i in range(n):
        if j == 1:  # 출발 열
            down[i][j] = max(up[i][j], down[i-1][j])    # 상승->하강, 아래
        elif i == 0:      # 천장
            down[i][j] = max(up[i][j], down[i][j-1])    # 상승->하강, 앞
        else:
            down[i][j] = max(up[i][j], down[i][j-1],
                             down[i-1][j])  # 상승->하강, 앞, 아래
        down[i][j] += scores[i][j]
print(down[n-1][m])

 

상승할 때의 최대 비행 점수를 저장하는 배열 up과 하강할 때 최대 비행 점수를 저장할 배열 down을 만든다. 그리고 다이나믹 프로그래밍 알고리즘을 이용하여 해당 배열의 값들을 구할건데 상승을 한 뒤에 하강을 하는 것이므로 up 배열의 값들

을 먼저 구하고 down 배열의 값들을 구할 것이다.

여기서 계산의 편의를 위해 가로 배열의 길이는 0~m-1이 아니라 1~m으로 한다.

 

1. 상승

이 문제에서 출발점은 (0, 1)이 아닌 (n-1, 1)이다. 그러므로 up[n-1][1]의 값을 scores[n-1][1]로 초기화해준다. 그리고 up 배열의 값들을 채워준다. up[i][j]는 1열 앞인 [i][j-1]에서 오는 값과 1행 아래인 [i+1][j]에서 오는 값 중 최대 값을 골라서 해당 칸을 지날 때의 비행 점수인 scores[i][j]를 더해주면 되는데, 이때 i==n-1일 때는 바닥에 해당하므로 그보다 아래에서 올 수는 없기에 1열 앞에서 오는 경우만 고려해준다.

 

2. 하강

출발열인 1열일 때, 천장(i==0)일 때, 그외 3가지 경우로 나누어서 값을 구한다. 3가지 경우의 공통점은 모두 해당 칸에서 상승에서 하강으로 전환될 수 있다는 점을 고려하여 up[i][j]와 값을 비교해야 된다는 점이다.

① 출발 열인 경우(j==1)에는 1행 아래로 내려가는 방법만 사용 가능하므로 down[i-1][j]을,

② 천장(i==0)인 경우에는 1열 뒤에서 앞으로 오는 방법만 사용 가능하므로 down[i][j-1]을,

③ 그 외의 경우에는 앞으로, 아래로 오는 경우를 모두 고려하여 down[i-1][j], down[i][j-1]을

up[i][j]와 비교하여 그 중 가장 큰 값을 찾아서 scores[i][j]와 더한 값을 down[i][j]에 저장하면 된다.