문제
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줄까지 숫자 삼각형이 주어진다.
출력
첫째 줄에는 최대가 되는 합을 출력한다.
예제 입력 복사
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
예제 출력 복사
30
/*
Problem : 숫자삼각형
Writer : J. I. Mun
Date : 20180129
Reference : http://jaeonysos.tistory.com
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
long long triangle[501][501] = { 0, };
long long dp[501][501] = { 0, };
int main(int argc, char * argv[]) {
int n;
long long max = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
scanf("%lld", &triangle[i][j]);
}
}
dp[1][1] = triangle[1][1];
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
if (dp[i][j] < dp[i - 1][j] + triangle[i][j])
dp[i][j] = dp[i - 1][j] + triangle[i][j];
if (dp[i][j + 1] < dp[i - 1][j] + triangle[i][j + 1])
dp[i][j + 1] = dp[i - 1][j] + triangle[i][j + 1];
}
}
for (int i = 1; i <= n; i++) {
if (dp[n][i] > max) max = dp[n][i];
}
printf("%lld\n", max);
return 0;
}
'Computer Science > Algorithm' 카테고리의 다른 글
[Algorithm/C] BOJ.1463 1로 만들기 (0) | 2018.02.01 |
---|---|
[Algorithm/C] BOJ.2579 계단 오르기 (0) | 2018.01.31 |
[Algorithm/C] BOJ.1546 평균 (0) | 2018.01.26 |
[Algorithm/C] BOJ.10871 X보다 작은 수 (0) | 2018.01.25 |
[Algorithm/C] BOJ.10817 세 수 (0) | 2018.01.24 |