[프로그래머스/Lv. 3] 정수 삼각형 (JAVA)

🔺 문제

프로그래머스

 

 

🔺 코드

import java.util.*;
 
class Solution {
    public int solution(int[][] triangle) {
        
        int[][] dp = new int[501][501];
        dp[0][0] = triangle[0][0];
        
        int max = 0;
        
        // 끝자리에 위치한 칸들 처리
        for(int i = 1 ; i < triangle.length ; i++) {
            dp[i][0] = dp[i-1][0] + triangle[i][0];
            dp[i][triangle[i].length - 1] = dp[i-1][i-1] + triangle[i][i];
        }
        
        // 중간에 위치한 칸들 처리
        for(int i = 1 ; i < triangle.length ; i++) {
            for(int j = 0 ; j < triangle[i].length ; j++) {
                if(j == 0 || j == i)    continue;
                
                dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
                max = Math.max(max, dp[i][j]);
            }
        }
        
        return max;
    }
}

 

 

🧩 해결 아이디어

• DP

: 양 끝에 위치한 경우와 중간에 위치한 경우 2가지로 나눠 생각한다.

 

1. 양 끝에 위치한 경우

 1) 맨 왼쪽에 위치한 경우, 바로 위쪽에 있는 값과 현재 칸 값을 더함

    (dp[i][j] = dp[i-1][0] + triangle[i][0])

 2) 맨 오른쪽에 위치한 경우, 바로 위쪽에 있는 값과 현재 칸 값을 더함

    (dp[i][j] = dp[i-1][i-1] + triangle[i][i])

 

2. 중간에 위치한 경우

: 왼쪽 위 값과 오른쪽 위 값 中 큰 값과 현재 칸 값을 더함

(dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j])

 

 

---

🔺 다른 풀이들

- dp배열 따로 만들지 않고, 기존의 triangle 배열만 활용하셨다.. 깔끔하시구나!!

import java.util.*;
class Solution {
    public int solution(int[][] triangle) {
        for (int i = 1; i < triangle.length; i++) {
            triangle[i][0] += triangle[i-1][0];
            triangle[i][i] += triangle[i-1][i-1];
            for (int j = 1; j < i; j++) 
                triangle[i][j] += Math.max(triangle[i-1][j-1], triangle[i-1][j]);
        }

        return Arrays.stream(triangle[triangle.length-1]).max().getAsInt();
    }
}

 

---

💬 느낀 점

이렇게 규칙이 빠르게 보이는 DP문제라면 언제든지 환영..

 

 

1회독	2회독	3회독	4회독	5회독
V