[BOJ] 1932 정수 삼각형

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

1932번: 정수 삼각형

알고리즘: DP

 

시간복잡도: O(N^2)

---

접근:

1. 이전 값들을 참고하면서 갱신하는 것이므로 Dynamic 문제

$$D[k]=MAX(D[k-i-1],\ D[k-i])+a_k$$

 

주의) 각 층의 양 끝점은 한 쪽 대각선이 없으므로 이를 예외 처리해줘야 함.

#include<stdio.h>
int main()
{
	int N, a, i, j, k, D[500*500], max = 0;
	
	scanf("%d", &N);
	
	scanf("%d", &D[0]);
	k = 1;
	max = D[0];
	for (i = 1; i < N; i++)
	{
		scanf("%d", &a);
		D[k] = D[k-i] + a;
		if (max < D[k]) max = D[k];
		k++;
		for (j = 1; j < i; j++)
		{
			scanf("%d", &a);
			D[k] = D[k-i-1] + a;
			if (D[k] < D[k-i] + a)
				D[k] = D[k-i] + a;
			if (max < D[k]) max = D[k];
			k++;
		}
		scanf("%d", &a);
		D[k] = D[k-i-1] + a;
		if (max < D[k]) max = D[k];
		k++;
	}
	printf("%d", max);
}