백준 1932 - 정수 삼각형

문제

 

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

1932번: 정수 삼각형

 

 

풀이

 

n번째 줄까지 값을 더했을 때 최대값을 찾아야하는 문제이다. i번째 줄에서 선택할 수 있는 숫자는 i-1번째에 있는 숫자들 중 대각선으로 연결된 두 숫자들이다. 이 두 숫자들 중에 최대를 골라서 더하면 i번째 줄까지 삼각형의 숫자들은 최대로 이루어지게 된다. 이 과정을 n번째 줄까지 반복을 하면 n번째 줄에는 최대값 경로로만 더해진 숫자들이 n개가 모이게 된다. 이 n개의 숫자중에서 최대를 고르면 n번째 경로까직 가는 최대 경로 값을 구할 수 있다.

 

 

코드

 

C++

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int dp[501][502];
int n;
int result;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> n;
 
    for (int i=1; i<=n; i++)
        for (int j=1; j<=i; j++)
            cin >> dp[i][j];
 
    for (int i=2; i<=n; i++)
        for (int j=1; j<=i; j++)
            dp[i][j] += max(dp[i-1][j], dp[i-1][j-1]);
        
    for (int i=1; i<=n; i++)
        result = max(result, dp[n][i]);
 
    cout << result;
 
    return 0;
}

 

python

n = int(input())
 
d = [[0] * n for _ in range(n)]
data = []
for _ in range(n):
    data.append(list(map(int, input().split())))
 
d[0][0] = data[0][0]
for i in range(1, n):
    for j in range(len(data[i])):
        if j == 0:
            d[i][j] += d[i-1][j] + data[i][j]
        elif j == len(d[i]) - 1:
            d[i][j] += d[i-1][j-1] + data[i][j]
        else:
            d[i][j] += max(d[i-1][j-1], d[i-1][j]) + data[i][j]
 
print(max(d[n-1]))