BaekJoon 1932 정수 삼각형

Link https://www.acmicpc.net/problem/1932

소스결과 2968 KB 32 ms

출처 BackJoon, IOI 1994 1번

언어 C++ 17

분류 다이나믹 프로그래밍

 

설명

DP에 대해서 공부해보자!

 

나올 수 있는 모든 경우의 수를 계산한다.! 하지만 옛 결과를 가지고 계산을 한다!

 

위 피라미드 문제가 DP에 대해서 학습하기는 편한거 같다.

 

위의 값에 대해서 왼쪽을 더했을때, 오른쪽을 더했을 때의 값 중 큰 값을 넣으면 된다.

눈에 보이는 대로 구현하자!

 

알고리즘

1. 피라미드를 입력 받는다.

2. 1번 줄부터 각 위치의 왼쪽, 오른쪽 값의 합을 더했을때 더 큰 경우를 현재 위치의 값으로 삼는다.

3. 피라미드중 가장 큰 값을 출력한다.

( 밑의 소스코드는 모든 배열을 탐색 하지만 범위가 0 ~ 9999 이므로 맨 밑의 배열만 검색해도 된다. )

 

소스코드

#include <iostream>

using namespace std;

const int MAX = 500;
int pyramid[MAX][MAX + 1];

int main()
{
	int n;

	cin >> n;

	for (int i = 0; i < n; i++)
		for (int j = 0; j <= i; j++)
			cin >> pyramid[i][j];

	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			if (j == 0)
				pyramid[i][j] += pyramid[i - 1][j];
			else
				pyramid[i][j] += pyramid[i - 1][j - 1] < pyramid[i - 1][j] ? pyramid[i - 1][j] : pyramid[i - 1][j - 1];
		}
	}

	int max = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j <= i; j++)
			if (pyramid[i][j] > max)
				max = pyramid[i][j];

	cout << max;

	return 0;
}