[백준 1932] 정수 삼각형 (C++/Java)

- C++

#include<cstdio>
#include<algorithm>
using namespace std;
int dp[501][501];
int main(void)
{
    int n,big=0;
    scanf("%d", &n);
    
    for (int i=1; i<=n; i++)
        for (int j=1; j<=i; j++)
            scanf("%d", &dp[i][j]);
    
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=i; j++) {
            if (j==1) dp[i][1]+=dp[i-1][1];
            else if (j==i) dp[i][j]+=dp[i-1][j-1];
            else
                dp[i][j]=dp[i][j]+max(dp[i-1][j-1], dp[i-1][j]);
            
            if (big<dp[i][j]) big=dp[i][j];
        }
    }
    printf("%d", big);
    return 0;
}

 

 

 

- JAVA

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n+1][n+1];
 
        for(int i=1; i<=n; i++){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=1; j<=i; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        for(int i=2; i<=n; i++){
            for(int j=1; j<=i; j++){
                if(j==1){
                    arr[i][j] = arr[i-1][j]+arr[i][j];
                } else if(j==i){
                    arr[i][j] = arr[i-1][j-1]+arr[i][j];
                } else {
                    arr[i][j] = Math.max(arr[i-1][j-1]+arr[i][j], arr[i-1][j]+arr[i][j]);
                }
            }
        }
 
        int ans=0;
        for(int i=1; i<=n; i++){
            ans = Math.max(ans, arr[n][i]);
        }
        System.out.println(ans);
    }
}