https://www.acmicpc.net/problem/1932
๋ฌธ์
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๋ฒ์งธ ์ค๊น์ง ์ ์ ์ผ๊ฐํ์ด ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ํฉ์ด ์ต๋๊ฐ ๋๋ ๊ฒฝ๋ก์ ์๋ ์์ ํฉ์ ์ถ๋ ฅํ๋ค.
ํ์ด
// Authored by : seondal
// Co-authored by : -
// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n;
cin >> n;
vector<vector<int>> v(n);
for(int i=0; i<n; i++){
for(int j=0; j<=i; j++) {
int input;
cin >> input;
v[i].push_back(input);
}
}
vector<vector<int>> dp(n, vector<int>(n));
dp[0][0] = v[0][0];
for(int i=1; i<n; i++) {
dp[i][0] = dp[i-1][0] + v[i][0];
for(int j=1; j<i; j++) {
dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + v[i][j];
}
dp[i][i] = dp[i-1][i-1] + v[i][i];
}
sort(dp[n-1].begin(), dp[n-1].end(), greater<>());
cout << dp[n-1][0];
return 0;
}
/*
*/
'๐ BOJ > Class 4' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ][C++] ๋ฐฑ์ค 9465๋ฒ: ์คํฐ์ปค (1) | 2023.04.18 |
---|---|
[BOJ][C++] ๋ฐฑ์ค 11725๋ฒ: ํธ๋ฆฌ์ ๋ถ๋ชจ ์ฐพ๊ธฐ (0) | 2023.03.24 |