[백준 1932] 정수 삼각형 (DP 풀이)

 

제한 사항

문제

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

예제

예제

 

---

나의 풀이

이 문제는 DP(다이나믹 프로그래밍)로 풀이할 수 있다.

Top-Down 방식이 있고, Bottom-Up 방식이 있다.

Top-Down 방식

탑다운 방식

이름 그대로 위 → 아래 방향으로 진행되는 방식이다.

위의 숫자가 밑의 숫자에 영향을 주는 것인데 만약 가장 바깥쪽이 아닌 중간 부분이라면 영향을 줄 수 있는 숫자가 2개 있을 것인데 그 중 큰 수를 더한다.

바깥쪽의 숫자들은 영향을 주는 숫자가 하나 밖에 없으므로 그냥 그 수를 더한다.

가장 바닥까지 내려왔다면 바닥에 있는 수 중 가장 큰 수가 답이 된다.

이 문제에서는 Top Down 방식보다는 Bottom Up 방식이 더 쉽고 간결하다.

 

Bottom-Up 방식

바텀업 방식

바텀업 방식은 밑의 두 수 중 더 큰 수를 더해 올라가는 방식이다.

위 그림을 보면 이해가 어렵지 않을 것이다 (만들기 너무 귀찮은 것...)

반복해서 위로 올라가다 보면 꼭대기에서는 하나의 숫자만 남게 되고, 그 수가 가장 큰 수가 된다.

탑다운 방식에 비해 코드도 훨씬 간결해지고 마지막에 최대값을 또 탐색해야 하는 비효율성도 없기 때문에 이 문제에서는 바텀업 방식으로 푸는 것이 더 적절하다고 생각한다.

소스 코드

n = int(input())
triangle = []
for _ in range(n):
    triangle.append(list(map(int, input().split())))
for i in range(n-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])

 

채점 결과