백준/1932/DP/정수 삼각형

백준/1932/DP/정수 삼각형

문제 해석

삼각형의 위에서 부터 아래로 내려올 때 경로의 값이 가장 큰 경로의 값을 구하는 문제입니다.

문제 풀이

위에 경로에서 내려올때는 대각선 오른쪽, 왼쪽으로 밖에 내려올 수 없습니다.
이를 표현하기 위해 우선 2차원 배열에 삼각형의 값들을 저장해줍니다.

int level = 0;
cin >> level;
for (int y = 0;y < level;y++)
{
	for (int x = 0;x < (y + 1);x++)
	{
		cin >> triangle[y][x];
	}
}

그리고 위에 경로에서 아래 경로를 내려오는 것은 왼쪽은 현재 자기 경로 바로 아래 오른쪽은 자기 경로에 x값을 +1 해주는 형태로 표현합니다. 그렇게 내려올 때 마다 경로의 최대 값을 저장해주면 다른 2차원 배열의 저장하면서 내려오면 됩니다.
간혹 겹치는 경로가 있다면 더 큰 값을 저장하면서 내려옵니다. 결국 이 문제에서 바라는 것은 경로의 값이 가장 큰 경로이니 작은 경로가 겹치면 작은 경로는 무시해도 됩니다.

for (int y = 0;y < level;y++)
{
	for (int x = 0;x < (y + 1);x++)
	{
		for (int z = x;z <= x + 1;z++)
		{
			if (result[y + 1][z] < result[y][x] + triangle[y + 1][z])
			{
				result[y + 1][z] = result[y][x] + triangle[y + 1][z];
			}
		}
	}
}

풀이

첫번째 풀이

#include<iostream>
using namespace std;

int triangle[501][501];
int result[501][501];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int level = 0;
	cin >> level;
	for (int y = 0;y < level;y++)
	{
		for (int x = 0;x < (y + 1);x++)
		{
			cin >> triangle[y][x];
		}
	}

	result[0][0] = triangle[0][0];

	for (int y = 0;y < level;y++)
	{
		for (int x = 0;x < (y + 1);x++)
		{
			for (int z = x;z <= x + 1;z++)
			{
				if (result[y + 1][z] < result[y][x] + triangle[y + 1][z])
				{
					result[y + 1][z] = result[y][x] + triangle[y + 1][z];
				}
			}
		}
	}

	int max_value = 0;
	for (int y = 0;y < level;y++)
	{
		if (max_value < result[level - 1][y])
		{
			max_value = result[level - 1][y];
		}
	}

	cout << max_value;

	return 0;
}