BOJ 1932: 정수 삼각형

#BOJ 1932: 정수 삼각형

1932번: 정수 삼각형

#풀이

보자마자 백트래킹으로 풀면 되겠다는 생각이 들었지만 지금은 dp를 연습하고 있어서 dp로 풀었다..

점화식을 만드는게 어려웠는데 생각해보니 은근 쉽다는 생각이 들었다.

d[i][j] = max(d[i-1][j], d[i-1][j-1]) + arr[i][j]

로 하면 점화식을 완성할 수 있다.

그 이유는 삼각형을 생각해보면 쉽다. 사실 문제에서는 인덱스를 생각하기가 쉽지 않은데

 

열에 숫자를 대입할 때 인덱스 1에서 부터 넣고 생각하면 쉽다.

그러면 아래에 있는 숫자를 더할 때 내가 d[i][j]를 선택할 수 있는 윗 열 중에 최대를 고르고 더하면 된다.

 

#코드

#include<iostream>
#include<algorithm>
using namespace std;
int n;
int arr[505][505];
int d[505][505];
int ans;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++)
			cin >> arr[i][j];
	}
	d[1][1] = arr[1][1];
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			d[i][j] = max(d[i-1][j], d[i-1][j - 1]) + arr[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		ans = ans < d[n][i] ? d[n][i] : ans;
	}
	cout << ans << '\n';
	return 0;
}