[백준] 1932번 : 정수 삼각형

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

해당 문제는 다이나믹 프로그래밍에 기본 문제로 탑다운 방식과 바톰업 방식을 둘다 풀어보겠습니다.

브루트포스 방식으로 문제를 해결 할 경우 모든경우의수를 탐색해야함으로 O(n^2) 이라는 시간복잡도를 갖게 됩니다.

 

 

 

1) 탑다운 방식

# 탑다운 방식
n = int(input()) # 삼각형의 크기
triangle = []
for _ in range(n):
    triangle.append(list(map(int, input().split())))

dp = [[0 for _ in range(n+1)]for _ in range(n)]
dp[0][0] = triangle[0][0]

for i in range(1, len(triangle)):
    for j in range(len(triangle[i])):
        dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
            
print(max(dp[n-1]))

 

2) 바톰업 방식

# 바텀업 방식
n = int(input()) # 삼각형의 크기
triangle = []
for _ in range(n):
    triangle.append(list(map(int, input().split())))
    
for i in range(len(triangle)-1, 0, -1):
    for j in range(len(triangle[i])-1):
        triangle[i-1][j] += max(triangle[i][j], triangle[i][j+1])
        
print(triangle[0][0])