[프로그래머스] 정수 삼각형 - 실패

- 실패한 시도

 

- 전 단계의 값들을 저장해 나가면서 하려고 했는데 

- 이는 전 단계에 값들이 얼마나 다음 단계로 퍼져나갈 지 예상이 어려우므로 내가 하는 방식이 아니라 다른 방식으로 해야한다.

 

 - 실패한 코드에서 배워나가자

 

 - dp && 최대값 문제 : 점화식 전 단계의 값을 어떻게 저장할 지 고민해야 함

 - 최대값이라면 모든 경우의 수가 아니라 전 단계에는 전 단계의 최대값만 필요

 

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        // idx = 0 -> 7
        // [7]
        // -------
        // idx = 0 -> 3 + 7
        // idx = 1 -> 8 + 7
        // [10, 15]
        // -------
        // idx = 0 -> 8 + 10
        // idx = 1 -> 1 + 10
        // idx = 1 -> 1 + 15
        // idx = 2 -> 0 + 15
        // [18, 11, 16, 15]
        // -------
        // idx = 0 -> 2 + 18
        // idx = 1 -> 7 + 18
        // idx = 1 -> 7 + 11
        // idx = 1 -> 7 + 16
        // idx = 2 -> 4 + 11
        // idx = 2 -> 4 + 16
        // idx = 2 -> 4 + 15
        // idx = 3 -> 4 + 15
        // [20, 25, 18, 23, 15, 20, 19, 19]
        
        // 현 단계 -> {idx}에도 더하고 {idx+1} 에 하나씩 더해져야 함
        // 결과 값 수 : 2^{triangle.length-1}
        int stageSize = triangle.length;
        int[] dp = new int[(int)Math.pow(2, stageSize -1)];
        for(int i=0; i<stageSize; i++) {
            int[] stageData = triangle[i];
            for(int j=0; j<stageData.length; j++) {
                int num = stageData[j];
                dp[j] += num;
                // dp[j] += num;
                // System.out.println(j);
                // System.out.println("-------00000------");
                // System.out.println(dp[j]);
                // System.out.println("-------00000------");
                System.out.println(num);
            }
            System.out.println("-------");
        }
        
        for(int num: dp) {
                System.out.println(num);
        }
        return answer;
    }
}