백준 1932 정수 삼각형

1) 2차원 배열을 이용해서 트리구조를 만들어보자.

2) 어떤 규칙인가

최대값들을 배열들이 저장하고 있으면 편하겠다. -> DP

arr[4][2]기준으로 생각해보자. 7은 왼쪽 대각선 위의 8을 받을수도 오른쪽 대각선 위의 1을 받을 수도 있다.

둘 중 큰 놈을 받으면 되는데, 확실한 건 7이 받을 수 있는 놈은 두놈 중 큰 한놈 뿐이다.

이를 식으로 나타내보면

arr[i][j] = max(arr[i-1][j-1], arr[i-1][j]) + arr[i][j] 이다.

여기서는 초기값 필요없는게

arr[1][1]이 처음 값인데 arr[0][0]이 모두 0으로 초기화 되어있어서 따로 초기값 필요없이 바로 찾아 나가면 된다.

 

 

트리구조는 2차원 배열로 만들면 되고,

가장 왼쪽이나, 가장 오른쪽에 위치한 놈들은 왼쪽 대각선 위나, 오른쪽 대각선 위가 없는데

2차원 배열에서는 그냥 0이니까 걍 무시하고 더해도 되는게 쉽게 풀 수 있었다.

#include <iostream>
using namespace std;

int max(int a, int b){
	return a>b ? a:b;
}

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