[백준] 1932번: 정수 삼각형

문제 내용

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

풀이 시간

5분

풀이 과정

DP를 이용한 간단한 풀이

 

정답 코드

 

1. 파이썬

import sys
sys_input=sys.stdin.readline

n=int(sys_input())

arr=[list(map(int,sys_input().rstrip().split())) for _ in range(n)]
dp=[[0]*i for i in range(1,n+1)]
dp[0][0]=arr[0][0]

for i in range(1,n):
    for j in range(0,i+1):
        if j==0:
            dp[i][j]=dp[i-1][j]+arr[i][j]
        elif j==i:
            dp[i][j]=dp[i-1][j-1]+arr[i][j]
        else:
            dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+arr[i][j]


print(max(dp[n-1]))

 

 

2. 자바

import java.io.*;
import java.util.*;

public class p1932 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][n];
        int[][] dp = new int[n][n];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int j = 0; j <= i; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
            Arrays.fill(dp[i], 0);
        }

        dp[0][0] = arr[0][0];

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0) {
                    dp[i][j] = dp[i - 1][j] + arr[i][j];
                } else if (j == i) {
                    dp[i][j] = dp[i - 1][j - 1] + arr[i][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + arr[i][j];
                }
            }
        }

        System.out.println(Arrays.stream(dp[n - 1]).max().getAsInt());
    }
}