[Java] 백준 4902 (삼각형의 값) Gold 2

Problem : https://www.acmicpc.net/problem/4902 4902번: 삼각형의 값 입력은 여러 개의 테스트 케이스로 이루어져 있고, 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 숫자는 줄의 수를 나타내고, 다음 숫자는 단위 삼각형에 적혀있는 값이 위에서 아래, 왼 www.acmicpc.net Approach 누적 합 개념과 구현이 합쳐진 문제였다. 먼저 누적 합 배열 preSum을 구성한다. preSum[i][j] 는 i행의 0 ~ j 열까지의 누적합을 저장한다. 문제에서는 정삼각형을 나타내지만 배열에 저장할 때는 아래 그림처럼 직각삼각형처럼 저장된다. 이제 파란 삼각형과 빨간 삼각형처럼 모든 만들 수 있는 삼각형의 합을 구하여 그 중 최댓값을 구해야 한다. 파란 삼각..