[프로그래머스 | Java Lv.3] 정수 삼각형 (DP, 동적 프로그래밍)

문제

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

프로그래머스

---

첫번째 제출 - dfs 사용 : 시간 초과

package week5.baek.dp;

import java.util.ArrayList;
import java.util.Collections;

public class Ex2 {
    static ArrayList<Integer> list = new ArrayList<>();

    public static void dfs(int[][] triangle, int i, int depth, int sum){
        if(depth == triangle.length) {
            list.add(sum);
        }
        else {
            dfs(triangle, i, depth + 1, sum + triangle[depth][i]);
            if(i+1 < depth)
                dfs(triangle, i + 1, depth + 1, sum + triangle[depth][i+1]);
        }
    }

    public static int solution(int[][] triangle) {
        dfs(triangle, 0,0, 0);
        Collections.sort(list);
        return list.get(list.size()-1);
    }

    public static void main(String[] args) {
        int[][] triangle = {{7}, {3, 8}, {8, 1, 0}, {2, 7, 4, 4}, {4, 5, 2, 6, 5}};
        System.out.println(solution(triangle));
    }

}

ㅇㅅㅇ

dfs 말고 dp로 풀어야했던 문제

 

---

접근

등굣길 문제(https://xoxoxoxox.tistory.com/227)와 도둑질 문제 (https://xoxoxoxox.tistory.com/229)을 짬뽕시킨 듯한 느낌

 

- 아래나 오른쪽 아래로 내려갈 수 있음

- 합이 더 큰 것을 기억해서 점점 내려가는 방식

 

- 왼쪽 끝(0번째 index)는 위에서부터 내려오는 방식만 가능

- 오른쪽 끝은 왼쪽 위에서부터 내려오는 방식만 가능

- 끝에 있지 않은 곳은 위, 왼쪽 위 둘 중 큰 것을 저장

        for (int i = 1; i < triangle.length; i++) {
            for (int j = 0; j < triangle[i].length; j++) {
                //왼쪽 끝일 때
                if(j == 0)
                    triangle[i][j] += triangle[i-1][j];
                //오른쪽 끝일 때
                else if(j == triangle[i].length-1)
                    triangle[i][j] += triangle[i-1][j-1];
                else
                    triangle[i][j] += Math.max(triangle[i-1][j], triangle[i-1][j-1]);
            }
        }

---

최종 코드

package week5.baek.dp;

import java.util.ArrayList;
import java.util.Collections;

public class Ex2 {
    public static int solution(int[][] triangle) {
        //두번째 줄부터 시작
        for (int i = 1; i < triangle.length; i++) {
            for (int j = 0; j < triangle[i].length; j++) {
                //왼쪽 끝일 때
                if(j == 0)
                    triangle[i][j] += triangle[i-1][j];
                //오른쪽 끝일 때
                else if(j == triangle[i].length-1)
                    triangle[i][j] += triangle[i-1][j-1];
                else
                    triangle[i][j] += Math.max(triangle[i-1][j], triangle[i-1][j-1]);
            }
        }

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

    public static void main(String[] args) {
        int[][] triangle = {{7}, {3, 8}, {8, 1, 0}, {2, 7, 4, 4}, {4, 5, 2, 6, 5}};
        System.out.println(solution(triangle));
    }

//    7
//    3 8
//    8 1 0
//    2 7 4 4
//    4 5 2 6 5
}

---

참고

https://easybrother0103.tistory.com/133

[알고리즘] 프로그래머스 - 정수 삼각형 - JAVA