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

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

정말 문제의 사진만 보더라도 가장 기본적인 DP의 문제중 하나이다.

문제를 푼 후, 다른 사람의 풀이를 참고해보니 이걸 Bottom-up 방식과 Top-down 방식으로 문제를 푼 것을 나눈 듯 한데, 굳이 따지고 풀진 않았으나 내 방식은 Bottom-up 방식에 속했다.

 

위에서부터 아래로 향할 때 합을 더해 나가는 방식으로 풀었으며 

이 같은 이미지가 나오면 

 

배열로는 

7

10 15

23 max(11,16),15

.

.

.

형식으로 배열을 채웠다.

음수가 없으므로 배열의 하단으로 갈 수록 무조건 큰 수가 될수밖에 없으며

이는 최하단 행을 읽으면 최댓값을 알 수 있게 된다는 의미이다.

 

아래는 코드 전문이다.

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        
        int[][] memo=new int[triangle.length][triangle.length];
        
        memo[0][0]=triangle[0][0];
        for(int row=1;row<triangle.length;row++){
            for(int col=0;col<triangle[row].length;col++){
                if(col==0){
                    memo[row][col]=memo[row-1][col]+triangle[row][col];
                } else if(col==row){
                    memo[row][col]=memo[row-1][col-1]+triangle[row][col];
                } else{
                    int left=memo[row-1][col-1]+triangle[row][col];
                    int right=memo[row-1][col]+triangle[row][col];
                    
                    memo[row][col]=Math.max(left,right);
                }
            }
        }
        for(int col=0;col<memo[triangle.length-1].length;col++){
            answer=Math.max(memo[triangle.length-1][col],answer);
        }        
        
        return answer;
    }
}