1932번 : 정수 삼각형

dp로 해결했습니다.

레벨을 i라고 할 때 그 전레벨인 i-1레벨에서 각각의 정수 j (i-1레벨에 대한 j는 총 i-1개만큼 있습니다)에 대한 dp를 해당 칸을 포함한 정수의 합의 최댓값으로 설정합니다. 즉 dp[i][j]는 그 전 레벨의 인접한 두 노드중 더 큰 값을 선택합니다.

여기서 arr[i][j]의 그 전레벨에 인접한 두 노드는 arr[i-1][j-1] 와 arr[i-1][j]입니다. ex)arr[3][2]의 그 전레벨에 인접한 두 노드는 arr[2][1]와 arr[2][2]가 됩니다.

하지만 여기서 한가지 생각해보아야 할 것은 arr[2][2]의 전레벨에 인접한 두 노드는 arr[1][1]과 arr[1][2]가 되어야 하는데 arr[1][2]에는 값이 없습니다. 이것은 초기화를 모두 삼각형에 들어갈 수 있는 범위인 0부터 9999의 최솟값인 0으로 해서 입력을 하면 모두 해결됩니다. arr[3][1]의 인접값도 arr[2][0]과 arr[2][1]이 되지만 arr[2][0]은 이미 0으로 초기화되어있기 때문에 값에는 지장이 없습니다.

따라서 arr[i][j]에 정수 삼각형을 입력받을 때, 식으로 보면 dp[i][j]=MAX(dp[i-1][j-1], dp[i-1][j])+arr[i][j]가 됩니다.

#include <stdio.h>

int dp[501][501], N, arr[501][501];

int MAX(int a, int b) {

return a > b ? a : b;

}

int f(int h, int n) {//높이가 h인 구간에서 n과 n+1을 비교해서 더 큰 값을 dp후보로.

return dp[h - 1][n] + MAX(arr[h][n], arr[h][n + 1]);

}

int main() {

scanf("%d", &N);

for (int i = 1; i <= N; ++i) {

for (int j = 1; j <= i; ++j) {

scanf("%d", &arr[i][j]);

}

}

dp[1][1] = arr[1][1];

for (int i = 2; i <= N; ++i) {

for (int j = 1; j <= i; ++j) {

dp[i][j] = MAX(dp[i - 1][j], dp[i - 1][j - 1]) + arr[i][j];

}

}

int max = -1;

for (int i = 1; i <= N; ++i) {

if (dp[N][i] > max) max = dp[N][i];

}

printf("%d", max);

}