알고리즘 문제
[C/C++ 백준 1932번] 정수 삼각형 (Silver 1)
새파란 공대생
2020. 5. 19. 01:45
https://www.acmicpc.net/problem/1932
1932번: 정수 삼각형
문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최�
www.acmicpc.net
처음에 dp를 일차원만으로 선언하고 싶었지만,,, 은근 까다로워 그냥 이차원으로 만들었다. dp[i][j]는 i번째 행의 j번째 숫자까지의 최대값을 의미한다. 점화식은 단순히 그 위의 두 숫자중 큰값에 그 자리 숫자를 더해주기만 하면 된다.
#include <cstdio>
#include <algorithm>
using namespace std;
int main(void){
int n, tri[501]={}, dp[501][501]={}, ans = -1;
scanf("%d",&n);
for(int i=1; i<=n; i++){
for(int j=1; j<=i; j++){
scanf("%d",&tri[j]);
dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+tri[j];
}
}
for(int k=1; k<=n; k++) ans=max(ans, dp[n][k]);
printf("%d", ans);
}