[C++] 백준 1932 : 정수 삼각형
#include <iostream>
using namespace std;
int main(void){
int n, maxNum = 0;
int arr[501][501]; // 값 입력 받는 arr 0 ~ 500
int dp[501][501] = {0}; // 합계 구할 arr 0 ~ 500
scanf("%d", &n);
for(int i = 1; i <= n; i++){ // 1부터 하는 이유는 인덱스 벗어나지 않게 하려고
for(int j = 1; j <= i; j++) {
scanf("%d", &arr[i][j]); //값 입력받기
}
}
dp[1][1] = arr[1][1]; // 첫째 줄 값
for(int i = 2; i <= n; i++){ // 삼각형 두번째 줄 부터 값 합산 시작
for(int j = 1; j <= i; j++){
dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + arr[i][j]; // 해당 인덱스와 그 전 줄에서 큰 것 합산
}
}
for(int i=0; i<=n; i++){
if(maxNum < dp[n][i]){ // 마지막 줄이 결과 값
maxNum = dp[n][i];
}
}
printf("%d", maxNum);
return 0;
}
오늘의 키포인트
-
파스칼의 삼각형을 이용한 문제.
백준 1010 다리놓기 문제와 굉장히 비슷하다. -
0부터 배열을 시작하면 0 - 1 이 인덱스의 범위를 벗어나기에 1부터 인덱스를 사용하도록 하였다.
-
위에서 아래로가 아니라 아래서 위로 생각하자. 합산값은 윗줄의 최대값과 자신의 값을 더한 것과 같다.
-
점화식
dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + arr[i][j];
Author And Source
이 문제에 관하여([C++] 백준 1932 : 정수 삼각형), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lamknh/C-백준-1932-정수-삼각형저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)