백준 BOJ 1932 - 정수 삼각형

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

1932번: 정수 삼각형

딱 보고 떠오른 방법은 위에서 내려가는 방법이겠지만

그러면 너무 시간이 오래 걸릴것 같아서

반대로 아래에서부터 올라오는 방식으로 짜보았다.

인접한 두가지를 비교해서 둘중 더 큰 숫자를 윗줄의 숫자에 더해주는걸 반복하면,

가장 큰 숫자가 제일 윗줄에 올라올것이고,

그 가장 윗줄만 출력해주면 된다.

 

#include <stdio.h>

int arr[1001][1001] = {0};

int main(){
	int n;
	scanf("%d", &n);
	for(int i=0; i<n; i++){
		for(int j=0; j<=i; j++){
			scanf("%d", &arr[i][j]);
		}
	}
	for(int i=n-1; i>0; i--){
		for(int j=1; j<n; j++){
			if(arr[i][j] > arr[i][j-1]) arr[i-1][j-1] += arr[i][j];
			else                        arr[i-1][j-1] += arr[i][j-1];
		}
	}
	printf("%d", arr[0][0]);
	return 0;
}

시험 5일남았는데 플밍하고있는거 실화?