[코딩테스트]백준 1932 정수 삼각형 - C++

✔ 문제

        7
      3   8
    8   1   0 
  2   7   4   4
4   5   2   6   5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

✔ 입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

✔ 출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

💖 문제풀이

DP 알고리즘을 이용하는 문제이다.
위 주어진 삼각형을 동적 이차원 배열로 설정하였고, 경로 탐색을 시작하였다.
갈 수 있는 경로는 좌측 대각선과 우측 대각선 뿐이므로, 2가지 경로를 비교하여
최댓값을 가지는 경로를 선택하여 누적 합으로 구한다.
이와 같은 방법은 삼각형의 수의 개수만큼만 탐색하면 최댓값을 구할 수 있게 해준다.

💖 C++ 코드

#include <iostream> 
#include <algorithm>
#include <cstring>

using namespace std; 

int dp(int** tri, int n ) {
	int max = 0;

	int** DP = new int* [n];
	for (int i = 0; i < n; i++) {
		DP[i] = new int[n];
		memset(DP[i], 0, sizeof(int) * n);
	}

	//0,0 값 초기화
	DP[0][0] = tri[0][0];

	//가장 왼쪽 경로 계산
	for (int i = 1; i < n; i++) {
		DP[i][0] = DP[i - 1][0] + tri[i][0];
	}

	for (int i = 0; i < n; i++) {
		for (int j = 1; j < i + 1; j++)
		{
			if (DP[i - 1][j - 1] > DP[i - 1][j]) {
				DP[i][j] = tri[i][j] +DP[i - 1][j - 1];
			}
			else
				DP[i][j] = tri[i][j] + DP[i - 1][j];
		}
	}

	max = *max_element(DP[n-1],DP[n-1]+n);

	return max;
}

int main() {

	int n; 
	cin >> n; 
	int answer; 

	int** h = new int* [n];
	for (int i = 0; i < n; i++) {
		h[i] = new int[n];
		memset(h[i], 0, sizeof(int) * n);
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			int temp; 
			cin >> temp; 
			h[i][j] = temp; 
		}
	}

	answer = dp(h,n);
	cout << answer; 
	return 0;
}

• memset 함수를 이용하기 위해서는 또는 <string.h> 헤더를
  추가해야한다. visual studio ide를 이용하는 경우 헤더를 추가하지 않아도 작동하나, 백준의 채점 환경은 이와 다르기 때문에 include 하지 않으면 컴파일에러가 난다.