(1932)(DP) 백준 숫자삼각형

https://www.acmicpc.net/problem/1932

풀이

---

arr[1][1]

arr[2][1]    arr[2][2]

arr[3][1]    arr[3][2]    arr[3][3]

arr[4][1]    arr[4][2]    arr[4][3]    arr[4][4]  <<------와 같은 구조로 이루어져있고 무조건 같은 단(행)에 있는 숫자중에 최대값만 따라 간다고 해서 결과값이 최대가 나오지 않는다는 것을 알 수 있다. 결국 모든 각각 배열공간에 위 값을 누적해서 넣어준다.

먼저 모든 연산을 식으로 정리해 본다면  3가지 경우로 나눌 수있다.

1. arr[1][1] -> arr[2][1] -> arr[3][1] -> arr[4][1] 과 같이 맨 왼쪽 배열만 따라서 누적해주는 경우

---

if(j == 1) arr[i][j] += arr[i-1][j];

2. arr[1][1] -> arr[2][2] -> arr[3][3] -> arr[4][4] 과 같이 맨 오른쪽 배열만 따라서 누적해주는 경우

---

if else(i == j) arr[i][j] += arr[i-1][j-1];

3. 위의 두가지 경우가 아닌 중간에 위치한 배열에 상위 값을 누적해줄 경우 

---

왼쪽 대각선과 오른쪽 대각선 값 2가지가 존재하므로 max함수를 만들어서 비교후 누적해준다.

else arr[i][j] += max(arr[i-1][j-1], arr[i-1][j]);

위의 코드가 핵심이다. 이를 종합하면 아래와 같은 답안 코드를 작성할 수 있다. 

실행시간을 줄이기 위해서 어떻게 해야하는지 생각해봤는데 결국 마지막 단에서 모든 배열에 대해서 연산을 해주고 마지막 단에서 max값을 찾는 방법 밖에 없었다.

#include <stdio.h>
 
int N;
int num[501][501] = { 0 };
int max(int a, int b) {
     return a > b ? a : b;
}
 
void InData() {
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= i; j++) {
            scanf("%d", &num[i][j]);
        }
    }
}
int main() {
    int Max = 0;
 
    InData();
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= i; j++) {
            if (j == 1) {
                num[i][j] += num[i - 1][j];
            }
            else if (i == j) {
                num[i][j] += num[i - 1][j - 1];
            }
            else {
                num[i][j] += max(num[i - 1][j - 1], num[i - 1][j]);
            }
            if (num[i][j] > Max) {
                Max = num[i][j];
            }
        }
    }
    printf("%d", Max);
}