AOJ - TRIANGLEPATH

AOJ - TRIANGLEPATH

단순한 DP 문제이고, $O(N^2)$ 으로 경로의 최대합을 찾아줄 수 있다.

void solve() {  
   int n;  
   cin >> n;  
   vvi a(n, vi(n));  
   for (int i = 0; i < n; i++) {  
      for (int j = 0; j <= i; j++) {  
         cin >> a[i][j];  
      }  
   }  
   vvi dp(n, vi(n));  
   int ans = 0;  
   dp[0][0] = a[0][0];  
   for (int y = 0; y < n - 1; y++) {  
      for (int x = 0; x < n; x++) {  
         dp[y + 1][x] = max(dp[y + 1][x], dp[y][x] + a[y + 1][x]);  
         dp[y + 1][x + 1] = max(dp[y + 1][x + 1], dp[y][x] + a[y + 1][x + 1]);  
      }  
   }  
   for (int i = 0; i < n; i++) ans = max(ans, dp[n - 1][i]);  
   cout << ans << endl;  
}