[C++] (백준 1932 번) 정수 삼각형

 

문제출처: 백준
문제 링크: https://www.acmicpc.net/problem/1932
난이도: ★★☆☆☆

• 문제 분류: 다이나믹 프로그래밍(dp)

[문제]

 

---

[분석]

보통의 DP의 문제처럼 bottom-up 방식으로 풀이하면 된다.

본인 위치에 합이 가장 큰 결과를 찾으려면 양쪽 대각선 위에 있는 것 중 최댓값을 찾아 해당값에 자신의 값을 더하는 방법으로 풀면 된다.

 

또한, 마지막 답을 구할 때, 마지막의 맨마지막 배열에 답이 있었던 기존 방식과 다르게 맨 마지막 N번째 배열의 1~n의 값들을 모두 비교해서 최댓값을 답으로 한다.

코드와 식의 간편성을 위하여 i=0 or j=0인 배열은 0으로 만들어서 따로 base case를 나누지 않더라도 답이 나올 수 있게 하였다.

 

• 점화식

  

---

[코드]

#include <iostream>
using namespace std;


unsigned long long num[501][501];
unsigned long long  s[501][501];
int main() {
	int n;
	unsigned long long max;
	cin>>n;
	for(int i=1;i<=n;i++){
	    for(int j=1;j<=i;j++) cin>>num[i][j];
	}
	
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            if(s[i-1][j-1]>s[i-1][j]) max=s[i-1][j-1];
            else max=s[i-1][j];
            s[i][j]=max+num[i][j];
           
            
        }
    
	}
	max=s[n][1];
	for(int i=2;i<=n;i++){
	    if(max<s[n][i]) max=s[n][i];
	}
	cout<<max<<endl;
	return 0;
}