백준 1932 풀이 (동적 계획법)

저번 문제가 1149 였는데 이때 굉장히 신기한 방식을 사용했다. 재귀로 풀어야할것 같은 최댓값 최소값을 구할때 뒤로 더해서 누적값을 만들어 주면 모든 경우를 염두하여 푸는 방식이 된다.

만약 이 삼각형의 각 층별 총합을 구하여 최댓값을 구하려면 재귀함수를 써야한다. 문제는 이러한 경우 재귀함수의 호출 갯수가 비약적으로 많아지게 된다는 것이다.

그래서 저번 1149 문제에서는 누적값을 만들어서 최솟값을 구했다. 이번에도 비슷한 방식으로 누적값을 만들어서 최댓값을 구하면된다.

 

아래에서 부터 어떤 선택을 할때 최댓값이 되는지 구하면서 올라가면 1층의 7은 최댓값으로 값이 변경된다.

코드는 굉장히 간단해진다.

n = int(input())
tmp = []
for _ in range(n):
    tmp.append(list(map(int,input().split())))

for i in range(n-2,-1,-1):
    for j in range(len(tmp[i])):
        tmp[i][j] += max(tmp[i+1][j],tmp[i+1][j+1])
print(tmp[0][0])