문제
위 그림은 크기가 5인 정수 삼각형의 한 모습이다.
맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.
삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.
입력
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
출력
첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.
|
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
|
#include<stdio.h>
int max(int a, int b) {
return a > b ? a : b;
}
int dp[501][501];
int triangle[501][501];
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]);
}
}
dp[1][1] = triangle[1][1];
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
if (j == 1)dp[i][j] = dp[i - 1][j] + triangle[i][j];
else if (i == j)dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
else dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
}
}
int max_num = 0;
for (int i = 1; i <= n; i++) {
if (dp[n][i] > max_num)max_num = dp[n][i];
}
printf("%d", max_num);
return 0;
}
|
cs |
간단한 dp 문제였다.
'백준 온라인 저지 (BOJ) 문제풀이' 카테고리의 다른 글
| 백준 온라인 저지 (BOJ) 12871 무한 문자열 (0) | 2020.09.24 |
|---|---|
| 백준 온라인 저지 (BOJ) 11051 이항계수 2 (0) | 2020.09.23 |
| 백준 온라인 저지 (BOJ) 10709 기상캐스터 (0) | 2020.09.23 |
| 백준 온라인 저지 (BOJ) 4108 지뢰찾기 (0) | 2020.09.23 |
| 백준 온라인 저지 (BOJ) 16198 에너지 모으기 (0) | 2020.09.23 |