1932) 정수 삼각형 (C++)

 출처 

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

1932번: 정수 삼각형

 내 풀이 

#include<iostream>

using namespace std;

int triangle[501][501];

int N = 0;	//삼각형의 크기



int main()
{
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < i + 1; j++)
		{
			cin >> triangle[i][j];
		}
	}

	// 윗값부터 더하기 위해 1부터 시작 
	for (int i = 1; i < N; i++)
	{
		for (int j = 0; j < i + 1; j++)
		{
			//맨 좌측일 경우 비교할 필요가 없음 
			if (j == 0)
			{
				triangle[i][j] += triangle[i - 1][j];
			}
			//맨 우측일 경우도 마찬가지 
			else if (j == i)
			{
				triangle[i][j] += triangle[i - 1][j - 1];
			}
			//그 외 중간 값들은 최고값을 비교해야함 
			else
			{
				triangle[i][j] = triangle[i][j] + max(triangle[i - 1][j], triangle[i - 1][j - 1]);
			}
		}
	}

	/* 잘 들어갔는지 체크 
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < i + 1; j++)
		{
			cout<< triangle[i][j];
		}
		cout << endl;
	}*/

	int result = triangle[N - 1][0];
	for (int i = 1; i < N; i++)
	{
		if (result < triangle[N - 1][i]) result = triangle[N - 1][i];
	}
	cout << result;
}

 해설

전에 풀었던 RGB문제와 비슷했다. 처음 값과 끝값을 제외하고 중간값부터 전에 있던 층의 좌측 우측 중 더 큰 수를

계속 더해줬다. 

 

 새로 안 것 

자신감