늘

문제부터 보면 전형적인 DP 문제라고 생각이 든다. 하지만 문제에 시간초를 보면 2초나 주어진다. 그래서 이 문제를 DP로 풀어야만 하는가 의문이 들면서 접근을 했다. 우선 문제 풀이 생각으로는 시간 제한도 2초이고 입력 수도 1000인것을 감안해서 넉넉하기 때문에 1일부터 Ti 시간만큼 뛰어가면서 전부 더해보는 방식으로 했다. #include #include #include using namespace std; int n; int visited[1001]; vector works; int answer; int pays; void start(int x, int pre) { if (x == n) { answer = max(answer, pays); return; } if (x > n) { answer = ..

전형적인 dp문제 중 한문제였다. 위에서 내려올때와 옆에서 올때의 두가지 경우로 dp[i][j]가 결정된다. #include #include #include using namespace std; int arr[301][301]; int dp[301][301]; int k; int main() { int n, m; cin >> n >> m; for (int i = 0; i > x >> y; arr[x][y] = m - (x + y); if (arr[x][y] < 0) { arr[x][y] = 0; } dp[x][y] = arr[x][y]; } for (int i = 1; i < 300; ++i) { for (int j = 1; j < 300; ++j) { d..

실버문제여서 만만히 보고 덤볐다고 시간좀 걸렸다. 왠지 자주 사용할것 같아서 한번 정리해두기로 하였다. #include #include using namespace std; int arr[10001]; int dp[10001]; int n; int main() { int k; cin >> n >> k; for (int i = 0; i > arr[i]; } dp[0] = 1; for (int i = 0; i < n; ++i) { for (int j = arr[i]; j

위상정렬 알고리즘을 통하여 해결하였다. 위상 정렬 알고리즘(Topology Sort)은 어떤 일을 하는 순서를 찾는 알고리즘이다. 방향 그래프에서 각 정점의 작업(?)수행 순서에 따라서 정렬은 한다고 볼 수 있다. #include #include #include #include using namespace std; int n, k; int time[1001]; int dp[100001]; int degree[100001]; vector v[100001]; int a, b, c; void clear() { for (int i = 1; i t; for (int x = 0; x > n >> k; for (int i = 1; i > time[i]; } for (int i = 1; ..

#include #include #include using namespace std; int dp[1000001]; vector v; int x; int main() { int n; cin >> n; v.push_back(-1000000001); for (int i = 0; i > x; if (v.back() < x) { v.push_back(x); } else { auto it = lower_bound(v.begin(), v.end(), x); *it = x; } } cout