[BOJ][C++] 백준 1932번 정수 삼각형

1932번 정수 삼각형

1. 문제 정보

백준 온라인 저지 [1932번 정수 삼각형] 문제의 링크입니다.

문제

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.
맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.
삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

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

출력

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

예제 입력1

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

예제 출력1

30

시간 / 메모리 제한

2초 / 128MB

---

2. 생각

1. 삼각형의 맨 꼭대기부터 향하며 수를 선택하여 합칩니다. 그 합이 최대가 되는 경로에 있는 수의 합을 출력합니다.
   dp[i]를 i층의 삼각형에서 합이 최대가 되는 경로라고 정의하겠습니다.

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

2. 위층에서 아래층으로 내려오며 각 수를 더한 값을 dp배열에 저장하겠습니다. 위의 배열로 볼 때 아래층에 있는 수의 입장에서는 위층의 있는 수를 합치거나 대각선 왼쪽 위에 있는 수를 합쳐야합니다.

3. 각 층에서 첫번째 수는 위층에서만 더할 수 있습니다.

   • dp[i][j] += dp[i - 1][j]

4. 각 층에서 마지막 수는 대각선 왼쪽 위의 수만 더할 수 있습니다.

   • dp[i][j] += dp[i - 1][j - 1]

5. 각 층에서 첫번째 수와 마지막 수를 제외한 수는 위층과 대각선 왼쪽 위의 수에서 더 큰 값을 합칩니다.

   • dp[i][j] += max(dp[i -1][j], dp[i - 1][j - 1])

6. 그리고 마지막 층에서는 n개의 경로가 나오고 그 경로중 가장 큰 값을 출력하면 문제에서 주어진 합이 최대가 되는 경로입니다.

• 참고 dp 배열

i\j	1	2	3	4	5
1	7
2	3+7 = 10	8+7 = 15
3	8+10 = 18	1+15 = 16	0+15 = 15
4	2+18 = 20	7+18 = 25	4+16 = 20	4+15 = 19
5	4+20 = 24	5+25 = 30	2+25 = 27	6+20 = 26	5+19 = 24

---

3. 소스코드 (C++)

---

터미널의 입출력 화면 예제1