[C++]BOJ 1932 - 정수 삼각형

삼각형 내부의 모든 지점에 dp를 수행하던 방향에 따라 그 전 층의 자신과 인접한 지점의 값 중 큰 값을 추가한다.

dp를 위에서 아래로 수행하는 방법과 아래에서 위로 수행하는 경우 두 가지를 가져와봤다.
결론은 아래에서 위가 더 효율적이다.

위에서 아래로

---

#include <iostream>
#include <algorithm>
using namespace std;
int n, m, dp[501][501];
int main() {
	cin >> n >> m;
	dp[1][1] = m;
	for(int i = 2; i <= n; i++) {
		for(int j = 1; j <= i; j++) {
			cin >> m;
			if(j == 1) dp[i][j] = dp[i - 1][j] + m;
			else if(j == i) dp[i][j] = dp[i - 1][j - 1] + m;
			else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + m;
		}
	}
	sort(dp[n] + 1, dp[n] + n + 1);
	cout << dp[n][n];
}

위에서 아래로 수행할 시 좌우 모서리 부분에 대한 예외처리가 필요하고, 또 마지막 바닥 줄에서 가장 큰 수를 찾아야 하므로 정렬이 필요했다.


하지만 아래에서 위로 수행하면 위의 두가지 단점을 해결해서 코드가 더 간결하다.

아래에서 위로

---

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
	int dp[501][501];
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= i; j++)
			cin >> dp[i][j];
	for(int i = n; i >= 1; i--)
		for(int j = 1; j <= i; j++)
			dp[i-1][j] += max(dp[i][j], dp[i][j+1]);
	cout << dp[1][1];
}

사실 처음에 생각해낸 방법이 위에서 아래로 방법이다.