[백준 1932] 정수 삼각형

 

 

간단한 dp 문제이다.

 

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

 

아래 인덱스는 위에 인접해 있는 인덱스 중 큰것을 골라 더해간다.

 

 

7
3+7	8+7
8+3+7	1+8+7	0+8+7
2+8+3+7	7+8+3+7	4+1+8+7	4+1+8+7
4+2+8+3+7	5+7+8+3+7	2+7+8+3+7	6+4+1+8+7	5+4+1+8+7

 

 

---

dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j];

---

점화식은 위와 같다.

 

dp[i][0] 일때는 -1의 인덱스로 접근할 수 있으므로 이것만 유의하면 된다.

 

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int a[][] = new int[n][n];
        int dp[][] = new int[n][n];
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<i+1; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        
        int max = 0;
        dp[0][0] = a[0][0];
        for(int i=1; i<n; i++) {
            for(int j=0; j<i+1; j++) {
                if(j==0)
                    dp[i][j] = dp[i-1][j] + a[i][j];
                else
                    dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j];
                if(max < dp[i][j])
                    max = dp[i][j];
            }
        }
        System.out.println(max);
    }
    
    public static int max(int a, int b) {
        return a > b ? a : b;
    }
}