백준 알고리즘 기초/다이내믹 프로그래밍
[백준][DP] 정수 삼각형
코딩고치
2020. 3. 25. 23:12
1. 문제 주소
https://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 이하이다. 삼각형을 이루고 있는 각 수는
www.acmicpc.net
2. 문제
정수 삼각형에서 수를 선택할 때 대각선 왼쪽 또는 오른쪽에 있는 수를 선택할 수 있으므로, i행 j열에 있는 수에 대해서 최대합을 구할 때 i-1행의 j-1열과 j열의 값을 비교하여 최대합을 구할 수 있다.
3. 소스코드
|
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
28
29
30
31
32
33
|
#include <iostream>
#include <algorithm>
using namespace std;
int num[501][501];
int dp[501][501];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
cin >> num[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + num[i][j];
}
}
int result = 0;
for (int j = 1; j <= n; j++) {
if (result < dp[n][j])
result = dp[n][j];
}
cout << result << '\n';
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|