[BOJ 1932] 정수 삼각형

문제 출처 : https://www.acmicpc.net/problem/1932

 

풀이 :

 

DP 문제입니다.

저는 위의 두개의 값을 비교하여 채워나가는 형식으로 짰습니다.

왼쪽과 오른쪽의 값중 큰것을 선택하여 그 셀에 합쳐 나가시면 됩니다.

#include<stdio.h>
#define max(A,B) ((A)>(B)?(A):(B))
int n, arr[500][500],ret,l,r;
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)for(int j=0;j<=i;j++)scanf("%d", &arr[i][j]);
    ret = arr[0][0];
    for (int i = 1; i < n; i++)for (int j = 0; j <= i; j++) {
        l = j > 0 ? arr[i - 1][j - 1] : 0;
        r = j < i ? arr[i - 1][j] : 0;
        arr[i][j] = arr[i][j] + max(l, r);
        if(i==n-1)ret = max(ret,arr[i][j]);
    }
    printf("%d", ret);
}