프로그래머스 - 정수삼각형/ 동적계획법/ dp/ 자바/JAVA

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

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

이문제는 딱보면 dfs/bfs인것 같기도 하다. 결국은 완전탐색인가

근데 그렇게 풀면 효율성 체크에서 문제가 생기겠지..?(사실 안해봐서 모름) 

그래서 나는 dp로 풀었다. dp문제니까 ㅎ

 

우선 처음값은 [0][0]에 저장해두었고

그다음값은 3개의 경우로 나눴다.

1)  첫번째 요소일때

2) 마지막 요소일때

3) 둘다 아닐때

 

삼각형의 첫번째는 이전 row의 첫번째로만 내려올 수 있다.

삼각형의 마지막요소는 이전 row의 마지막으로만 내려올 수 있다.

나머지는 다 두개씩 가능하다. ( j-1또는 j로)

 

그래서 첫번째랑 마지막 요소는 이전값에서 현재값을 더해준 다음 저장해주었고,

3)의 경우는 max를 사용해 두값을 비교해서 더 큰값을 저장해주었다. 

어차피 가장 큰 값을 고르는 거니까 작은값은 저장할 필요가 없다.

그때그때 큰값을 선택해서 골라주고

마지막에 가장 route[size-1]을 정렬해서

큰값을 골라냈다.

 

import java.util.Arrays;
import java.util.Collections;
class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int size = triangle.length;
        int [][] route = new int[size][];
        
        for(int i=0;i<size;i++){
            route[i] = new int[i+2];
        }
        route[0][0] = triangle[0][0];
        
        for(int i =1;i<size;i++){
            for(int j=0;j<=i; j++){
                if(j==0){
                    route[i][j] = route[i-1][j]+triangle[i][j];
                }
                else if(j==i){
                    route[i][j] = route[i-1][j-1]+triangle[i][j];
                }
                else{
                    route[i][j] =Math.max(route[i-1][j-1], route[i-1][j])+ triangle[i][j];
                }
            }
        }
        Arrays.sort(route[size-1]);
        answer= route[size-1][size];
        
        return answer;
    }
}