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

 

1) 문제설명

백준 Online Judge 1932번 정수 삼각형

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

1932번: 정수 삼각형

 

2) 아이디어

 

삼각형에서 DP [줄][몇 번째 숫자] = 합의 최대로 설정하고 0으로 초기화한다.

반복문을 2개 돌려서 DP의 최댓값을 체크한다.

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;
long long dp[501][501]={0,};

int main() {
	int n;
	long long arr[501][501];
	cin >> n;
	
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			cin >> arr[i][j];
			
		}
		
	}

	dp[0][0] = arr[0][0];
	dp[1][0] = arr[0][0];

	long long maxt = arr[0][0];
	for (int i = 1; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			
			dp[i][j] = max(dp[i - 1][j] + arr[i][j], dp[i - 1][j - 1] + arr[i][j]);
			if (maxt < dp[i][j]) {
				maxt = dp[i][j];
			}
			
		}
		
	}
	cout << maxt << endl;
}

처음에 입력을 1차원 배열로 받아서 힙 구조로 접근을 하였는데 구현이 쉽지가 않아서 2차원 배열로 다시 접근했더니 간단하게 풀렸다.