[백준] 1932번 정수 삼각형

문제 링크

 

풀이

이차원 배열도 일차원 배열처럼 연속된 메모리에 지나지 않지만 개발자가 작업할 때는 직관적으로 접근할 수 있어서 편합니다. 이 문제를 이차원 배열로 풀면 조금 편합니다. 예제로 주어진 입력값을 이차원 배열을 이용해 다음처럼 할 수 있습니다. 

이 배열은 점화식을 위한 이차원 배열이며 dp[3][2]는 [3][2] 위치까지 합산된 최대값을 표현합니다. 즉 dp[2][1]과 dp[2][2]를 비교해서 더 큰 값을 [3][2]의 좌표의 값과 더해서 dp[3][2]를 갱신하면 됩니다. 점화식은 다음과 같습니다.

 

d[i][j] = max(d[i-1][j-1], d[i-1][j]) + triangle[i][j]

 

반복문 사용을 최소화하기 위해 triangle 이차원 배열을 선언하지 않고 일차원 배열을 하나 선언해 입력을 받을 때마다 갱신할 수 있도록 했습니다.

 

코드

#include <cstdio>
#include <vector>
using namespace std;
int main()
{
	int N;
	scanf("%d", &N);
	vector<vector<int>> d(N+1, vector<int>(N+1, 0));
	vector<int> t(N+1, 0);
	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= i; ++j)
		{
			scanf("%d", &t[j]);
			int a = d[i - 1][j - 1];
			int b = d[i - 1][j];
			d[i][j] = (a > b ? a : b) + t[j];
		}
	}
	int max = 0;
	for (int i = 1; i <= N; ++i)
	{
		auto val = d[N][i];
		max = max < val ? val : max;
	}
	printf("%d", max);
}