프로그래머스-정수삼각형

아래와 같이 나타낼 수 있는 int[][] = {{7},{3,8},{8,1,0},{2,7,4,4},{4,5,2,6,5}} 배열이 있다.

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중,

거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

입출력 예

 int[][] triangle = {{7},{3,8},{8,1,0},{2,7,4,4},{4,5,2,6,5}} 

for(i=1; i<triangle.length; i++){ //바깥 for문은 행의 개수
    for(int j=0; j<i+1; j++){ // 내부 for문은 열의 개수. 그런데 n행의 열의 개수는 n개이다.
       if(j==0){
		       trinangle[i][j] = triangle[i][j] +  triangle[i-1][j];
       } else if(j==triangle[i].length-1){
		       triangle[i][j] = triangle[i][j] + triangle[i-1][j-1];
       } else{
		       triangle[i][j] = triangle[i][j] + Math.max(triangle[i-1][j-1],triangle[i-1][j])
       
       }
    int max = Arrays.stream(triangle[trianlge.length-1]).max().getasInt;
    //값이 누적되어 오니 최대값은 항상 제일 밑에 행에 있으니 제일 밑의 행의 최댓값을 출력하면 된다.
    
    }
}

-->for문이 관건인 문제다.
일단 로직은 위 꼭지점에 있는 7부터 시작하니 각 자리에 누적된 합으로 초기화 시키는 것이다.
그러면 문제에서말하는 1행과 2행은           7    은   7    이 된다.
                                         3  8     10  15 
                                         
그 다음행이 문제인데 제일 양 사이드에 있는 값은 그대로 누적하면 되지만,
중간에 있는 값은 현재값에서 10을 더할 지 18을 더할지 선택해야하는데 이때는 당연히 둘 중 최대값을 
골라 더해줘야한다.