백준 1932번 - 정수 삼각형

최대의 합을 찾아가는 문제다. 백트래킹으로 구현할 수 있지만, 이 문제 또한 DP문제이기 때문에 시간 초과를 생각하고 문제를 풀어야 한다. 위에서 아래로 내려가면서 합을 더해주면서 진행하면 밑의 값이 무엇이 올 지 모르기 때문에, 모든 경우를 다 생각해야 한다. 반면에, 아래에서 위로 올라가면서 합을 갱신하면 모든 경우를 돌지 않아도 된다. 이런 방식은 이전에 풀었던 RGB거리 문제(https://aodtns.tistory.com/20)와 유사하다. 

백준 1149번 - RGB거리

 

 

##변수 선언 부분##
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거리를 풀고 나니 그렇게 어렵지 않은 문제였지만, 갱신하는 방식을 모르고 풀었다면 못 풀었을 것 같다.