(c++)프로그래머스 코딩테스트 연습 - 정수 삼각형

programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

[풀이]

정확성과 효율성을 둘 다 보는 문제여서 DP를 이용해 풀었다.

바닥부터 꼭대기까지 각 숫자를 선택했을 때 그 숫자 밑으로 얻을 수 있는 최댓값을 저장하면서 올라갔다.

dp[0][0]에는 거쳐간 숫자의 최댓값이 저장된다.

#include <string>
#include <vector>

using namespace std;

int **dp;
int Level;
int dp_size;

void DP(vector<vector<int>>triangle) {
	for (int i = 0; i < Level; i++)
		dp[Level - 1][i] = triangle[Level - 1][i];
	//바닥부터 위로 올라가면서 최댓값 저장
	for (int i = Level - 2; i >= 0; i--) {
		for (int j = 0; j <= i; j++) {
			dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];
		}
	}
}

int solution(vector<vector<int>> triangle) {
	int answer = 0;
	Level = triangle.size();
	dp_size = triangle.back().size();
	//dp 배열 동적할당
	dp = new int*[dp_size];
	for (int i = 0; i < dp_size; i++) {
		dp[i] = new int[dp_size];
	}
	DP(triangle);
	answer = dp[0][0];
	for (int i = 0; i < dp_size; i++) {
		delete[] dp[i];
	}
	delete[] dp;
	return answer;
}