21923번: 곡예 비행
동헌이는 모형 비행기 조종 대회에 참가하였다. 이 대회에서는 격자 모양의 공간에서 모형 비행기를 조종하여 얻는 비행 점수로 순위를 매긴다. 격자의 각 칸에는 점수가 부여되어 있고, 비행
www.acmicpc.net
코드
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]에 저장하면 된다.
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 백준 16432번 떡장수와 호랑이 (0) | 2024.05.04 |
---|---|
[Python/파이썬] 백준 14430번 자원 캐기 (2) | 2024.04.27 |
[Python/파이썬] 백준 15993번 1, 2, 3 더하기 8 (1) | 2024.04.25 |
[Python/파이썬] 백준 2157번 여행 (0) | 2024.04.24 |
[Python/파이썬] 백준 1757번 달려달려 (0) | 2024.04.09 |