정수 삼각형(JAVA)

문제

프로그래머스

삼각형 꼭데기에서 시작해 바닥까지 가면서 숫자를 더해 최댓값을 구하는 문제이다.

내려갈때는 항상 대각선 아래로만 내려갈 수 있다.

import java.util.*;
class Solution {
    int [][]dp = new int[501][501];
    public int solution(int[][] triangle) {
        for(int a[] : dp) //이차원 배열 모두 -1로 초기화
            Arrays.fill(a, -1);
        dp[0][0]=triangle[0][0];
        for(int i=1;i<triangle.length;i++){
            for(int j=0;j<triangle[i-1].length;j++){
                for(int k = j;k< j+2;k++){
                    if(dp[i][k]==-1) //아직 아무도 안지나갔기 때문에 -1이다.
                        dp[i][k] = triangle[i][k]+dp[i-1][j];
                    else if(dp[i][j]!= -1){ //이미 지나갔으므로 서로 비교해줘야 한다
                        dp[i][k] = max(dp[i][k], triangle[i][k]+dp[i-1][j]);
                    }
                }
            }
        }
        int answer = 0;
        for(int i : dp[triangle.length-1]){ //마지막 바닥에서 최댓값을 구함
            answer = max(answer, i);
        }
        return answer;
    }
    public int max(int a, int b){
        if(a>b)return a;
        else return b;
    }
}

다른 사람의 풀이

import java.util.*;
class Solution {
    public int solution(int[][] triangle) {
        for (int i = 1; i < triangle.length; i++) {
            triangle[i][0] += triangle[i-1][0];
            triangle[i][i] += triangle[i-1][i-1];
            for (int j = 1; j < i; j++) 
                triangle[i][j] += Math.max(triangle[i-1][j-1], triangle[i-1][j]);
        }

        return Arrays.stream(triangle[triangle.length-1]).max().getAsInt();
    }
}

첫번째 for문에서는 서로 비교할 것이 없는 삼각형 중에서 양 끝에 대각선을 초기화 해주는 것이다.

두번째 for문에서는 서로 비교할 것이 있는 삼각형 중에서 양 끝에 대각선을 제외한 중간에 있는 것들을 비교해

주는 것이다.

마지막 줄은 바닥에 해당하는 행에서 최댓값을 return 해주는 것이다.