백준 1932 정수 삼각형 c++

문제 출처 : www.acmicpc.net/problem/1932

1932번: 정수 삼각형

문제

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

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

알고리즘 분류

• 다이나믹 프로그래밍

풀이

dp문제다.

맨 위층부터 시작해서 한 줄씩 내려오면서 선택된 수의 합을 구하는 문제다.

합을 저장하기 위한 triangle[501][500]배열을 선언하고, 해당 칸마다, 맨 위층부터 더해진 수를 저장한다.

이때, 더해진 수의 최댓값을 구하는 문제기 때문에, 더해진 수중 더 큰 수를 저장한다.

i번째 줄에 수가 i개 있을때,

triangle[i][0]은 triangle[i-1][0]+ 현재 칸에 들어온 수

triangle[i][i]은 triangle[i-1][i-1]+ 현재 칸에 들어온 수

(줄의 맨 앞의 수와 맨 뒤의 수는 윗 줄의 양 끝에서만 더해질 수 있기 때문)

triangle[i][j]은 triangle[i-1][j-1] 와 triangle[i-1][j] 중 큰 수 + 현재 칸에 들어온 수

 

이걸 반복문으로 코드화하고, 마지막 줄인 triangle[n][0]~triangle[n][n]중 큰 수를 출력하면 된다.

 

 

코드

#include<iostream>
#include<algorithm>

using namespace std;

int triangle[501][500];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (i == 1) {
                cin >> triangle[i][j];
            }
            else {
                int num;
                cin >> num;
                if (j == 0)
                    triangle[i][j]=num+triangle[i - 1][j];
                else if(j==i-1) {
                    triangle[i][j] =num+ triangle[i - 1][j - 1];
                }
                else {
                    triangle[i][j] = num + max(triangle[i - 1][j - 1], triangle[i - 1][j]);
                }
            }
        }

    }
    int ans = triangle[n][0];
    for (int i = 1; i <= n; i++) {
        ans = max(ans, triangle[n][i]);
    }
    cout << ans;
    return 0;
}