문제
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번째 줄까지 정수 삼각형이 주어진다.
출력
첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.
예제 입력 1
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 |
예제 출력 1
30 |
더보기
Solution
#include<stdio.h>
#include<stdlib.h>
int main(void)
{
int n, **triangle=NULL, **max=NULL, max_number;
scanf("%d", &n);
triangle=(int **)malloc(n*sizeof(int *));
for(int i=0;i<n;i++)
triangle[i]=(int *)malloc((i+1)*sizeof(int));
max=(int **)malloc(n*sizeof(int *));
for(int i=0;i<n;i++)
max[i]=(int *)calloc(i+1,sizeof(int));
for(int i=0;i<n;i++)
for(int j=0;j<=i;j++)
scanf("%d", &triangle[i][j]);
max[0][0]=triangle[0][0];
for(int i=1;i<n;i++)
{
max[i][0]=max[i-1][0]+triangle[i][0];
max[i][i]=max[i-1][i-1]+triangle[i][i];
}
for(int i=1;i<n;i++)
for(int j=1;j<i;j++)
max[i][j]=triangle[i][j]+(max[i-1][j-1]>max[i-1][j]?max[i-1][j-1]:max[i-1][j]);
max_number=max[n-1][0];
for(int i=1;i<n;i++)
max_number=max[n-1][i]>max_number?max[n-1][i]:max_number;
printf("%d\n", max_number);
for(int i=0;i<n;i++)
free(max[i]);
free(max);
for(int i=0;i<n;i++)
free(triangle[i]);
free(triangle);
return 0;
}
728x90
'백준 알고리즘' 카테고리의 다른 글
<백준 알고리즘> 15894번: 수학은 체육과목 입니다 (0) | 2020.10.22 |
---|---|
<백준 알고리즘> 2864번: 5와 6의 차이 (0) | 2020.10.22 |
<백준 알고리즘> 1158번: 요세푸스 문제 (0) | 2020.10.21 |
<백준 알고리즘> 2167번: 2차원 배열의 합 (0) | 2020.10.20 |
<백준 알고리즘> 11048번: 이동하기 (0) | 2020.10.20 |