백준 1932 정수삼각형

www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;


int main()
{	
	cin >> n;
	vector <vector <int>> arr(n+1);

	int tmp;

	for (int i = 1; i <= n; i++)
	{
		arr[i].push_back(0);
		for (int j = 1; j <= i; j++)
		{
			cin >> tmp;
			arr[i].push_back(tmp);
		}
		arr[i].push_back(0);//양옆으로 0추가
	}
	//입력완료

	arr[0].push_back(0);
	arr[0].push_back(0);
	arr[0].push_back(0);//범위이탈방지

	vector <vector <int>> copy(n + 1);
	copy = arr;//대충복사

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			if (i == 1 || i == 2)//처음 두칸은 더해놓은게 없으니 arr로
				copy[i][j] += max(arr[i - 1][j - 1], arr[i - 1][j]);
			else//이후는 위에서 더한 값들을 재사용-->copy배열이용
				copy[i][j] += max(copy[i - 1][j - 1], copy[i - 1][j]);
		}

	}

	cout<<*max_element(copy[n].begin(), copy[n].end());



}

 

배열을 딱딱하게 생각하지 않고 트리 구조로 그려서 공통식을 찾아보았는데 바로 나왔다

다만 트릭으로는 범위를 넘어 오류를 방지하기 위해서 양 옆에 0을 추가하고 arr[1][]부터 값을 넣었기 때문에 arr[0][]에 0을 세번 추가해줬다는점?

그렇게 복잡한 알고리즘이 아닌데 시간이 많이 나와  ios::sync_with_stdio(false); cin.tie(NULL); 두문장 추가해주니 줄었다.. 

cin.tie(NULL);