[C++] BOJ-1932

 

문제풀이

---

1. 가장 왼쪽에 있는 숫자와 가장 오른쪽에 있는 숫자는 경우의 수가 하나이기 때문에 바로 위에 배치된 숫자만 더하면 된다.

 

2. 그 외의 숫자들은 모든 경우의 수를 계산해서 가장 큰 수를 다음 줄에 저장한다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
	int n;
	cin >> n;
	int dp[501][501];
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j <= i; j++){
			cin >> dp[i][j]; 
		}
	}
	
	for(int i = 1; i<n; i++){
		for(int j = 0; j<=i; j++){
			if(j==0) dp[i][j] += dp[i-1][j];
			else if(j==i) dp[i][j] += dp[i-1][j-1];
			else{
				dp[i][j] = max(dp[i-1][j-1]+dp[i][j],dp[i-1][j]+dp[i][j]);
			}
		}
	}
	
	int m = 0;
	
	for(int i = 1; i<n; i++){
		if(dp[n-1][i] > m){
			m = dp[n-1][i];
		}
	}
	
	cout << m;
}