[백준 1932번] 정수 삼각형

문제 링크: 1932번 정수 삼각형

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

 

아랫층의 수는 윗층의 수 중 왼쪽 대각선과 오른쪽 대각선의 수만 고를 수 있다. 그리고 이것이 배열로 들어올 때는 아랫층 수가 a[row][col]이라면 왼쪽 대각선의 수는 a[row][col-1], 오른쪽 대각선의 수는 a[row][col]이다. 위에서부터 아래로 내려오면서, 윗층의 수 중 큰 것과 아랫층의 수를 더해서 저장하면 된다. 구현을 편리하게 하기 위해 triangle의 폭을 n+2로 선언하고 값을 입력받기 전 triangle을 -1(또는 0)로 초기화해두면 반드시 triangle 내의 숫자만 고려되기 때문에 왼쪽 끝과 오른쪽 끝을 신경쓸 필요가 없다.

 

C/CPP

#include <stdio.h>
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int n, a[501][502];

int main(void) {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            scanf("%d", &(a[i][j]));
        }
        for (int j = 1; j <= i; j++) {
            a[i][j] = a[i][j] + MAX(a[i - 1][j - 1], a[i - 1][j]);
        }
    }
    int mx = 0;
    for (int i = 1; i <= n; i++) {
        mx = MAX(mx, a[n][i]);
    }
    printf("%d", mx);
    return 0;
}

 

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int[][] triangle;
    static int[][] sum;

    public static int max(int a, int b) {
        if (a > b) return a;
        return b;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);        
        int n = sc.nextInt();

        // triangle의 열을 n+2로 하여, 양 끝값을 신경쓰지 않아도 되도록 한다.
        triangle = new int[n][n+2];

        // triangle -1로 채우기
        for (int i = 0; i < n; i++)
            Arrays.fill(triangle[i], -1);

        // triangle 입력받기
        for (int i = 0; i < n; i++)
            for (int j = 1; j < i+2; j++)
                triangle[i][j] = sc.nextInt();

        // 대각선 왼쪽 또는 대각선 오른쪽 값 중 큰 값과 자신을 더해서 누적합을 만든다.
        for (int i = 1; i < n; i++)
            for (int j = 1; j < i+2; j++)
                triangle[i][j] = max(triangle[i-1][j-1], triangle[i-1][j]) + triangle[i][j];

        // 누적값의 마지막 행에서 가장 큰 값을 출력한다.
        int[] last = triangle[n-1];
        Arrays.sort(last);
        System.out.println(last[last.length-1]);

        sc.close();
    }
}