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

1. 문제

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

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

 

2. 설명

그림1. 정수 삼각형

아래로 합을 계산해 나가는 방식으로 풀었다.

2가지로 나뉘는데

그림2. 경우의 수가 삼각형 양쪽 끝일 경우

이 경우에는 어차피 한가지 경우의 수들 밖에 없어서 j==0일 때랑 j==i일 때로 나눠서 구했고

나머지는 합이 더 큰 부분으로 내려가도록 구했다.

그림3. 안쪽 부분일 경우

↑나머지 부분들

 

그러면 결과가

7

10 15

18 16 15

20 25 20 19

24 30 27 26 24

이렇게 나오고, 마지막 배열에서 최댓값을 구해서 답을 구했다.

 

3. 코드

import java.util.*;
class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int height = triangle.length;

        for(int i=1; i<height; i++) {
            for(int j=0; j<=i; j++) {
                if(j==0) {
                    triangle[i][j] += triangle[i-1][j];
                } else if(j==i) {
                    triangle[i][j] += triangle[i-1][j-1];
                } else {
                    triangle[i][j] += max(triangle[i-1][j-1],triangle[i-1][j]);
                }
            }
            
        }
        // 최댓값
        for(int i=0; i<height; i++) {
            answer = max(answer,triangle[height-1][i]);
        }
        
        return answer;
    }
    private int max(int a, int b) {
        return a > b ? a : b;
    }
}