BOJ 1932 정수 삼각형 (다이나믹 프로그래밍 기초)

 

요즘 DP를 연습하고 있다. Bottom-Up이던 Top-Down이

던 생각이 나면 풀려고 하고 있지만 아무래도 근본 없이 문제를 막 푸는 나로서는 Bottom-Up을 통해 조금씩 조금씩 해결해 나가는 것이 좋은 것 같다. 근데 이게 실버급 문제라서 망정이지 골드급의 문제이면 나는 어떡할까. 가슴이 웅장해진다.

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
	int LC;
	int** line;
	int** DP;
	cin >> LC;
	line = (int**)malloc(sizeof(int*) * (LC + 1));
	DP = (int**)malloc(sizeof(int*) * (LC + 1));
	for (int i = 0; i < LC; i++)
	{
		line[i] = (int*)malloc(sizeof(int) * (i + 1));
		DP[i] = (int*)malloc(sizeof(int) * (LC + 1));
		for (int j = 0; j <= i; j++)
		{
			cin >> line[i][j];
		}
	}
	for (int i = 0; i < LC; i++)
	{
		DP[LC - 1][i] = line[LC - 1][i];
	}
	for (int i = LC-2; i >= 0; i--)
	{
		for (int j = 0; j <= i; j++)
		{
			DP[i][j] = max(DP[i + 1][j], DP[i + 1][j + 1]) + line[i][j];
		}
	}
	cout << DP[0][0];
	return 0;
}

1932.pdf

0.50MB

이건 내 의식의 흐름이다.