BOJ 1932 숫자삼각형(C++)

숫자삼각형 성공

한국어원문

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	3437	2000	1574	60.960%

문제

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

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

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

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

입력

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

출력

첫째 줄에는 최대가 되는 합을 출력한다.

예제 입력 

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

예제 출력 

30

힌트

출처

Olympiad > International Olympiad in Informatics > IOI 1994 1번

• 데이터를 추가한 사람: hwangtmdals
• 문제의 오타를 찾은 사람: Martian

링크

• PKU Judge Online
• Sphere Online Judge

알고리즘 분류

• 다이나믹 프로그래밍

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

#include    <stdio.h> #include    <algorithm> #pragma warning(disable : 4996)   static int triangle[555][555];   int main() {     int n;     scanf("%d", &n);       for (int i = 1; i <= n; ++i)     for (int j = 1; j <= i; ++j)         scanf("%d", &triangle[i][j]);       for (int i = n; i >= 1; --i)     {         for (int j = 1; j <= i; ++j)         {             triangle[i - 1][j] += std::max(triangle[i][j], triangle[i][j + 1]);         }     }       printf("%d", triangle[1][1]);       return 0; }

여러 방법이 있을 것 같다. 

다이나믹 프로그래밍의 가장 쉬운 형태.

보통 위에서 아래로 내려가면서 큰 수를 찾아서 더하는 방법도 있으나 그 방법을 이용하면 최대값이 가장 아래에 나오게 된다. 

7

3 8

8 1 0 

2 7 4 4

4 5 2 6 5 -> 여기 답이 나오게 됨

그러면 결국 아래에서 한번 더 sort 또는 최대값을 찾는 일이 필요하다. 

그래서 아래에서부터 올라오면서 더 큰 값을 위에 더해주는 방법으로 하면 가장 위쪽에 답이 나오게 된다.

7 -> 여기 답이 나오게 됨

3 8

8 1 0 

2 7 4 4

4 5 2 6 5