[백준] 1932번 : 정수 삼각형 [C/C++]

#문제

1932번: 정수 삼각형

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

1932번: 정수 삼각형

 

---

#접근방법

삼각형의 제일 밑층에서 위로 올라가면서 둘 중에 큰 값을 누적시키는 것을 반복하면 맨 위에 있는 곳이 정답이 된다.

반응형

---

#풀이

#include <stdio.h>
#include <algorithm>
using namespace std;

int arr[505][505];

int main(){
	int n;
	
	scanf("%d",&n);
	
	for(int i=0;i<n;i++)
		for(int j=0;j<i+1;j++)
			scanf("%d",&arr[i][j]);
	
	for(int i=n-1;i>=1;i--)
		for(int j=0;j<i;j++)
			arr[i-1][j] += max(arr[i][j],arr[i][j+1]);
	
	printf("%d",arr[0][0]);
	
	return 0;
}

 

제일 아래층부터 위층으로 올라가면서 arr[i][j]와 arr[i][j+1] 둘 중에 큰 값을 arr[i-1][j]에 누적시키는 것을 반복하면 제일 꼭대기층 arr[0][0]이 정답이 된다.

---

#성능

---

#정리

이전에 구했던 값을 재사용하는 다이다믹 프로그래밍 기법을 알고 있으며, 이를 구현할 수 있으면 풀 수 있는 문제였다.