BOJ 1932 정수 삼각형

www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

간단한 DP 문제였다.

삼각형이

 

n = 5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

 

이런 식으로 주어진다면 가장 밑 줄에서 가장 큰 수를 얻으려면 

0번째 줄에서 그다음 줄로 현재 값에서 왼쪽으로 내려가던가, 오른쪽으로 내려가던가 이 두 가지 경우의 수만

따져주면 된다.

 

max(solve(x + 1, y + 1), solve(x + 1, y)) + ar[x][y]

 

table[x][y] 의 값은 결국 위의 식처럼 될 것이다.

 

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

int ar[501][501], d[501][501], n;

int solve(int x, int y) {
	if (x == n - 1) return ar[x][y];
	if (d[x][y] != -1) return d[x][y];

	return d[x][y] = max(solve(x + 1, y + 1), solve(x + 1, y)) + ar[x][y];
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> n;

	memset(d, -1, sizeof(d));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			cin >> ar[i][j];
		}
	}

	cout << solve(0, 0) << endl;

	return 0;
}

 

삼각형이 0이 될 수 있으므로 -1로 초기화해줘야 안전할 것 같아서 memset으로 초기화해줬다.