코딩 테스트 - 정수 삼각형

대박!

라이브 코딩테스트에서 나온 문제임 (<<<랑 >>> 짜는데 오래 걸렸었음... )

카메라 켜놓고 봤던 시험이라 손발이 부들부들...

아무튼 보통 이렇게 짤 것이다...

↓ 요롷게...

package programmers;

public class 정수삼각형_221231 {

    public static void main(String[] args) {

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

        System.out.println(solution(triangle));

    }

   

    public static int solution(int[][] triangle) {

        int answer = 0;

        int len = triangle.length;

        int[][] arr = new int[len][len];        

       

        for (int i = 0; i < len; i++) {

            if(i == 0){

                arr[0][0] = triangle[0][0];

            }else{

                // <>

                for (int j = 1; j <= i; j++) {

                    arr[i][j] = Math.max(arr[i-1][j], arr[i-1][j-1]) + triangle[i][j];

                }

                // <<<<

                arr[i][0] = arr[i-1][0] + triangle[i][0];

                // >>>>

                arr[i][i] = arr[i-1][i-1] + triangle[i][i];

            }            

        }

       

        for (int i = 0; i < len; i++) {

            answer = Math.max(answer, arr[len-1][i]);

        }

       

        return answer;

    }

}

아무튼 ↓이렇게 짠 사람 대단하당.

arr 배열을 안  만들고 짰음!