[백준/BOJ/알고리즘/파이썬(python)/C++]#1932_정수 삼각형

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

1932번: 정수 삼각형

그리디 알고리즘으로 DP로 짜면 되는 문제다.

어렵게 자꾸 생각하니까 로직이 막 꼬이고 한참 헤맸다...휴

그냥 단순하게 생각해도 되는 문제는 단순하게 생각하자!

 

파이썬 코드

import sys
input = sys.stdin.readline

n = int(input())
tri = []

for _ in range(0, n):
    tri.append(list(map(int, input().split())))

row = 2
for i in range(1, n):
    for j in range(row):
        if j==0: #맨 왼쪽 번호
            tri[i][j] +=  tri[i-1][j]
        elif j==len(tri[i])-1: #맨 오른쪽 번호 
            tri[i][j] +=  tri[i-1][j-1]
        else:#그 사이
            tri[i][j] += max(tri[i-1][j],tri[i-1][j-1])
    row += 1

print(max(tri[n-1]))

C++ 코드

#include<iostream>
#include<algorithm>
using namespace std;
int tri[501][501]={0,};
int arr[501][501]={0,};
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			cin>>tri[i][j];
		}
	}
	
	int res=0;
	for (int i = 1; i <=n; i++) {
		for (int j =1; j <=n; j++) {
			arr[i][j] += max(arr[i - 1][j - 1], arr[i - 1][j]) + tri[i][j];
			res = max(res, arr[i][j]);
		}
	}
	cout << res;




}