프로그래머스 - 정수 삼각형 [자바]

• 문제 링크 : 정수 삼각형

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

 

정답(Solution)

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int temp = -1;
        int[][] t = triangle;

        for(int i=0; i<t.length - 1; i++){
            for(int j=0; j<t[i].length; j++){
                if(temp != -1){
                    t[i+1][j] = t[i+1][j] > temp + t[i][j] ? 
                    t[i+1][j] : temp + t[i][j];
                }else{
                    t[i+1][j] = t[i+1][j] + t[i][j];
                }
                temp = t[i+1][j+1];
                t[i+1][j+1] = t[i+1][j+1] + t[i][j];
            }
            temp = -1;
        }

        int len = t.length;
        for(int i=0; i<t[len-1].length; i++){
            answer = Math.max(answer, t[len-1][i]);
        }
        return answer;
    }
}

 

분석

이중 for문을 돌면서 i번째의 t[i][j] 를 i+1 번째의 t[i+1][j], t[i+1][j+1]에 더해준다.

예를 들어
j = 0 일때의 t[i+1][j+1] 와 j = 1일 때의 t[i+1][j] 가 동일한 변수이므로 그대로 더해줄 경우 2번 더하게 된다.

그래서 temp 변수를 -1로 선언하여 -1일 경우 t[i+1][j]에 t[i][j]를 더해주고
temp = t[i+1][j]를 할당하여 더해주기 전 값을 임시로 저장해둔다.
그리고 t[i+1][j+1] 에 t[i][j] 를 더해주고 다음 반복으로 넘어간다.
다음 반복(loop)에서 temp가 -1이 아니므로 현재 t[i+1][j]와 temp + t[i][j]를 비교하여 더 큰 값을 재할당한다.

위와 같이 반복문을 수행하면 조건과 일치하는 결과를 만들 수 있다.

마지막 행에서 가장 큰 수를 찾으면 정답을 찾을 수 있다.

 

참고할 만한 정답

 

• 아래에서 위의 2개 값 더하기

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0; //max
        int[][] t = triangle;

        for(int i=1; i<t.length; i++){
            for(int j=0; j<t[i].length; j++){
                if(j == 0){
                    t[i][j] = t[i][j] + t[i - 1][j];
                }else if(i == j){
                    t[i][j] = t[i][j] + t[i - 1][j -1];
                }else{
                    int left = t[i][j] = t[i][j] + t[i - 1][j -1];
                    int right = t[i][j] = t[i][j] + t[i - 1][j];

                    t[i][j] = Math.max(left, right);
                }

                answer = Math.max(answer, t[i][j]);
            }
        }

        return answer;
    }
}

 

• 역으로 제일 밑에서 부터 상위의 1개에 값 더하기(역발상)

class Solution {
    public int solution(int[][] triangle) {
        int[][] t = triangle;

        for(int i = t.length - 2; i>=0; i--){ // t.length -2는 가장 마지막 라인의 위쪽부터 계산되기 때문
            for(int j=0; j<t[i].length; j++){

                int left = t[i][j] + t[i+1][j];
                int right = t[i][j] + t[i+1][j+1];

                t[i][j] = Math.max(left, right);
            }
        }

        return t[0]; //역으로 더하기 때문에 가장 초기값에 max 값이 더해짐
    }
}

 

비교 분석

• 역발상으로 풀이한 정답이 가장 깔끔하게 풀이할 수 있는 방법이다.