[ALGOSPOT] 알고스팟: 삼각형 위의 최대 경로

https://www.algospot.com/judge/problem/read/TRIANGLEPATH

algospot.com :: TRIANGLEPATH

 

#include <bits/stdc++.h>
using namespace std;

int C, n, tri[101][101], dp[101][101];

int solve(){
	// dp[i][j] : (i,j)까지의 최대합
	// dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + tri[i][j];
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= i; j++){
			dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + tri[i][j];
		}
	}
	return *max_element(dp[n] + 1, dp[n] + n + 1);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> C;
	while(C--){
		memset(dp, 0, sizeof(dp));
		cin >> n;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= i; j++){
				cin >> tri[i][j];
			}
		}
		cout << solve() << '\n';
	}
}

 

[BOJ] 1932번: 정수삼각형 문항과 유사한 문항입니다.

소스 코드의 주석과 같이 dp table을 정의하면 점화식을 쉽게 세울 수 있습니다.

1-based index를 선호하는데, 자교 문병로 교수님의 알고리즘 강의를 듣고 영향을 받았습니다. i = 0 or j = 0 부분이 경계치 역할을 하여 따로 추가해야할 초기값 설정을 굳이 해주지 않아도 된다는 장점이 있습니다.