[Java] 프로그래머스 - 정수 삼각형 (3단계)

코딩 테스트 풀이 체크리스트
2시간 내에 풀었는가?	O
본인의 실력으로 풀었는가?	O

 

코딩테스트 연습 - 정수 삼각형

 

 

 

 

 

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        //합계를 구해서 담을 배열
        int[][] sBoard = new int[triangle.length][triangle.length];
        sBoard[0][0] = triangle[0][0];
        
        for (int i = 1; i < triangle.length; i++) {
            만약 3번째 행이면 3번째 열까지만 가면 되기 때문에 범위 설정함
            for (int j = 0; j <= i; j++) {
                sBoard[i][j] = Math.max(sBoard[i][j], sBoard[i-1][j] + triangle[i][j]);
                if (j == 0) continue;
                sBoard[i][j] = Math.max(sBoard[i][j], sBoard[i-1][j-1] + triangle[i][j]);
            }
            
            if (i == triangle.length - 1) {
                for (int j = 0; j <= i; j++) {
                    answer = Math.max(answer, sBoard[i][j]);
                }
            }
        }
        return answer;
    }
}

 

정확성 테스트

테스트 1 〉	통과 (0.04ms, 75.2MB)
테스트 2 〉	통과 (0.03ms, 75.9MB)
테스트 3 〉	통과 (0.05ms, 76.9MB)
테스트 4 〉	통과 (0.08ms, 74.5MB)
테스트 5 〉	통과 (0.58ms, 74MB)
테스트 6 〉	통과 (0.13ms, 73.5MB)
테스트 7 〉	통과 (0.38ms, 67.9MB)
테스트 8 〉	통과 (0.11ms, 78.9MB)
테스트 9 〉	통과 (0.03ms, 77.8MB)
테스트 10 〉	통과 (0.09ms, 75.9MB)

효율성 테스트

테스트 1 〉	통과 (14.73ms, 61.2MB)
테스트 2 〉	통과 (11.26ms, 63.1MB)
테스트 3 〉	통과 (12.07ms, 61.5MB)
테스트 4 〉	통과 (7.95ms, 60.9MB)
테스트 5 〉	통과 (11.59ms, 61.5MB)
테스트 6 〉	통과 (13.98ms, 61.6MB)
테스트 7 〉	통과 (13.37ms, 64MB)
테스트 8 〉	통과 (10.53ms, 57MB)
테스트 9 〉	통과 (14.63ms, 74.5MB)
테스트 10 〉	통과 (12.15ms, 61.6MB)