요즘 DP를 연습하고 있다. Bottom-Up이던 Top-Down이
던 생각이 나면 풀려고 하고 있지만 아무래도 근본 없이 문제를 막 푸는 나로서는 Bottom-Up을 통해 조금씩 조금씩 해결해 나가는 것이 좋은 것 같다. 근데 이게 실버급 문제라서 망정이지 골드급의 문제이면 나는 어떡할까. 가슴이 웅장해진다.
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int LC;
int** line;
int** DP;
cin >> LC;
line = (int**)malloc(sizeof(int*) * (LC + 1));
DP = (int**)malloc(sizeof(int*) * (LC + 1));
for (int i = 0; i < LC; i++)
{
line[i] = (int*)malloc(sizeof(int) * (i + 1));
DP[i] = (int*)malloc(sizeof(int) * (LC + 1));
for (int j = 0; j <= i; j++)
{
cin >> line[i][j];
}
}
for (int i = 0; i < LC; i++)
{
DP[LC - 1][i] = line[LC - 1][i];
}
for (int i = LC-2; i >= 0; i--)
{
for (int j = 0; j <= i; j++)
{
DP[i][j] = max(DP[i + 1][j], DP[i + 1][j + 1]) + line[i][j];
}
}
cout << DP[0][0];
return 0;
}
이건 내 의식의 흐름이다.
'vidigummy KAU > 알고리즘 공부(백준!)' 카테고리의 다른 글
BOJ11724(연결요소의 개수) (0) | 2020.07.31 |
---|---|
그래프 (BFS, DFS 구현) (0) | 2020.07.30 |
BOJ 9020(골드바흐의 추측) (0) | 2020.07.11 |
으이구! BOJ-1316 (0) | 2020.07.07 |