최대의 합을 찾아가는 문제다. 백트래킹으로 구현할 수 있지만, 이 문제 또한 DP문제이기 때문에 시간 초과를 생각하고 문제를 풀어야 한다. 위에서 아래로 내려가면서 합을 더해주면서 진행하면 밑의 값이 무엇이 올 지 모르기 때문에, 모든 경우를 다 생각해야 한다. 반면에, 아래에서 위로 올라가면서 합을 갱신하면 모든 경우를 돌지 않아도 된다. 이런 방식은 이전에 풀었던 RGB거리 문제(https://aodtns.tistory.com/20)와 유사하다.
##변수 선언 부분##
t = []
##메인 함수 부분##
if __name__ == "__main__":
N = int(input())
t = [[int(x) for x in input().split()]for y in range(N)]
for i in range(N-1,0,-1): #N-1번째부터 위로 올라가면서 진행
for j in range(i): #i번 만큼 max를 구해준다.
t[i-1][j] = max(t[i][j],t[i][j+1]) + t[i-1][j]
print(t[0][0])
RGB거리를 풀고 나니 그렇게 어렵지 않은 문제였지만, 갱신하는 방식을 모르고 풀었다면 못 풀었을 것 같다.
'백준 문제풀이(파이썬) > 동적 계획법 1' 카테고리의 다른 글
백준 1463번 - 1로 만들기 (0) | 2021.06.04 |
---|---|
백준 2579번 - 계단 오르기 (0) | 2021.06.04 |
백준 1149번 - RGB거리 (0) | 2021.06.01 |
백준 9461번 - 파도반 수열 (0) | 2021.06.01 |
백준 9184번 - 신나는 함수 실행 (0) | 2021.05.31 |