728x90
https://www.acmicpc.net/problem/1932
오랜만에 푼 DP(다이나믹 프로그래밍)문제다.
우선 삼각형을 입력 받아준다. 입력값들의 길이가 1,2,3,... 순으로 증가하므로 2차원 벡터를 이용해 입력 받았다.
그런 다음, 초기값을 설정해주는 것이 중요한데 dp[1][0]은 삼각형의 맨 첫번째 값(=꼭대기 값)이고 dp[1][1]은 원래 존재하지 않는 값이지만 점화식을 생성 및 이용하기 위해 0으로 설정해주었다.
초기값(삼각형 1층)에 대한 설정이 끝났으므로, 그 아래 줄인 삼각형 2층부터 점화식을 이용해 최대값을 저장해주면 된다.
다만, 맨 왼쪽은 항상 바로 위의 값과 더해짐을 유의해주자.
또한 dp배열을 main문 바깥에 정의하였기 때문에 이 배열은 자동으로 0으로 초기화 된다. 때문에 맨 오른쪽 값을 더할 때, 범위가 벗어나도 그 값이 0이므로 지장이 없는 것! 이해가 안된다면 아래 사진을 보자
점화식에 대해 설명하자면, DP는 보통 직전에 구한 값들이 다음 값 계산에 영향을 미친다. 그렇기 때문에 dp 배열에는 그 순간 순간 마다의 최댓값을 저장해놓으면 된다
문제의 예제중 일부를 살펴보자.
위 그림처럼 dp 배열에는 각 층에서 가질 수 있는 최댓값을 저장해주는 것이다!
여기서 16이란 수는 10(7+3) +1 과 15(7+8)+1 중 최댓값을 선택한 것이다.
#include <iostream>
#include <vector>
typedef long long ll;
using namespace std;
int n,num;
vector<int> v[510];
int dp[510][510];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
for(int i=1; i<=n;i++){
for(int j=1; j<=i;j++){
cin >> num;
v[i].push_back(num);
}
}
dp[1][0] = v[1][0];
dp[1][1] = 0;
for(int i=2;i<=n;i++){
dp[i][0] = dp[i-1][0] +v[i][0];
for(int j=1; j<v[i].size();j++){
dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + v[i][j];
}
}
int ans=-1;
for(int i=0; i<v[n].size();i++){
ans = max(ans,dp[n][i]);
}
cout << ans;
}
728x90
'알고리즘 > 백준(BOJ)' 카테고리의 다른 글
[백준/C++] 7569번 토마토 (0) | 2022.09.30 |
---|---|
[백준/C++] 1600번 말이 되고픈 원숭이 (0) | 2022.09.30 |
[백준/C++] 16927번 배열 돌리기 2 (0) | 2022.09.30 |
[백준/C++] 16509번 장군 (0) | 2022.09.30 |
[백준/C++] 11779번 최소비용 구하기2 (0) | 2022.09.30 |