pushback

자. 삼각형을 살짝 바꾸자.

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

이 삼각형을

7
3   8
8   1   0
2   7   4   4
4   5   2   6   5

이렇게. 풀기 훨씬 쉬워졌다.

dp[n][k]는 (0,0)에서 (n, k)까지 가면서 선택된 수들의 최대 합이라고 하자.

n-1번째 행에서 (n, k)로 올 수 있는 좌표는 (n-1, k-1)와 (n-1, k)이다.

dp[n][k]는 최댓값을 저장해야하기 때문에 dp[n-1][k-1]와 dp[n-1][k] 중 더 큰 값을 선택하고 (n, k) 좌표에 저장된 수를 더해주면 된다.

결국 점화식은

dp[n][k] = max(dp[n-1][k-1], dp[n-1][k]) + num[n][k]

가 된다.

이제 코딩하자.

어.. 근데.. n이 0부터 시작하게 되면 n-1가 음수가 안되도록 따로 처리해주어야 한다.. k-1도 마찬가지.

귀찮다. 삼각형을 다시 한번 바꿔보자

0
0   7
0   3   8
0   8   1   0
0   2   7   4   4
0   4   5   2   6   5

이제 (0, 0)이 아니라 (1, 1)부터 시작하자.

이렇게 해도 문제가 없을까 ? 없다.

최댓값을 찾는 문제이기 때문에 가장 앞에 있는 0이 선택 될 일은 없다.

진짜 코딩하자.

#include <bits/stdc++.h>
using namespace std;

int dp[502][502];
int num[502][502];

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

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

	for (int i = 1; i <= n; ++i) for (int j = 1; j <= i; ++j) {
		dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + num[i][j];
	}
	
	// 최댓값을 찾자.
	int ans = 0;
	for (int i = 1; i <= n; ++i) ans = max(ans, dp[n][i]);
	
	cout << ans;

	return 0;
}

위에 코드를 보면 음.. num이 필요없어 보인다. 살짝 최적화를 해보자.

#include <bits/stdc++.h>
using namespace std;

int dp[502][502];

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	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 = 1; i <= n; ++i) for (int j = 1; j <= i; ++j) {
		dp[i][j] += max(dp[i - 1][j - 1], dp[i - 1][j]);
	}
	
	int ans = 0;
	for (int i = 1; i <= n; ++i) ans = max(ans, dp[n][i]);
	
	cout << ans;

	return 0;
}