[백준 1932번 C/C++] 정수 삼각형

 

 

목차

 

 

---

 

 

[백준 1932번 C/C++] 정수 삼각형

 

 

---

 

해결방안

 

Dynamic Programming(DP)

 

---

 

코드

 

#include<stdio.h>
#include<algorithm>
using namespace std;

int tri[501][501], sum[501][501];

int main() {
	int n, maxValue=0;
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			scanf("%d", &tri[i][j]);
		}
	}

	sum[0][0] = tri[0][0];

	for (int i = 1; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			if (j == 0) {
				sum[i][j] = sum[i-1][j] + tri[i][j];
			}
			else if (j == i) {
				sum[i][j] = sum[i-1][j-1] + tri[i][j]; 
			}
			else {
				sum[i][j] = max(sum[i-1][j-1], sum[i-1][j]) + tri[i][j];
			}
		}
	}

	for (int i = 0; i < n; i++) {
		maxValue = max(maxValue, sum[n - 1][i]);
	}

	printf("%d", maxValue);

	return 0;
}

 

 

 

#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;

int n;
int tri[501][501], cache[501][501], nextLoc[501][501];

int path(int y, int x)
{
    if (y == n) return 0;

    int& ret = cache[y][x];

    if (ret != -1) return ret;

    // 경로 기록
    {
        int nextBottomLeft = path(y + 1, x);
        int nextBottomRight = path(y + 1, x + 1);

        if (nextBottomLeft > nextBottomRight) nextLoc[y][x] = x;
        else nextLoc[y][x] = x + 1;
    }

    return ret = tri[y][x] + max(path(y + 1, x), path(y + 1, x + 1));
}

int main() {
    scanf("%d", &n);

    memset(cache, -1, sizeof(cache));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            scanf("%d", &tri[i][j]);
        }
    }

    int ret = path(0, 0);

    printf("%d", ret);

    return 0;
}