[백준/C++] 1932 정수 삼각형 (S1)

유형	난이도	완료일	링크	특이사항
DP	실버1	23/02/19	https://www.acmicpc.net/problem/1932

 

 

내 코드

#include <iostream>
#include <algorithm>

using namespace std;

int arr[501][501];
int n;

int main(void)
{
	cin >> n;
	
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<=i; j++)
		{
			cin >> arr[i][j];
		}
	}
	
	for(int i=n-2; i >= 0; i--)
	{
		for(int j=0; j<=i; j++ )
		{
			arr[i][j]+= max(arr[i+1][j],arr[i+1][j+1]);
		}
	}
	
	cout << arr[0][0];
	
}

앞서 고생해서 푼 ‘RGB거리’ 문제와 비슷한 점이 있어 쉽게 해결했다.

삼각형의 맨 밑에서부터 반복문을 돌렸다. arr[i][j]와 arr[i][j+1] 중 더 큰 값을 arr[i-1][j]에 더해가면서 누적 합을 구하는 방식으로 계산했고, 결국 마지막엔 삼각형 꼭대기의 하나의 숫자만 남아 arr[0][0]에 최댓값이 저장된다.

쉽게 금방 풀려서 뿌듯했다.