oVeron

DP Knuth Optimization 기본 문제.#include using namespace std;typedef long long ll;typedef pair pii;typedef pair pll;typedef tuple tiii;const int INF = 1e9;const int MAXK = 5001;int K;int dp[MAXK][MAXK];int pos[MAXK][MAXK];int psum[MAXK];void solve(){ fill(&dp[0][0], &dp[MAXK-1][MAXK], INF); cin >> K; for(int i=1; i> fi; dp[i][i] = 0; pos[i][i] = i; psum[i] = psum[i-..

알고리즘/baekjoon 2024. 8. 15. 22:53

DP - Divide and Conquer Optimization 기본 문제#include using namespace std;typedef long long ll;typedef pair pii;typedef pair pll;typedef tuple tiii;const ll INF = 1e18;const int MAXL = 8001;const int MAXG = 801;int L, G;ll psum[MAXL];ll dp[MAXG][MAXL]; //dp[i][j] : i번째 간수까지 j번째 칸을 감시할 때 탈옥 위험도의 최솟값//s, e : dp[i][m]를 최소로 만들어 주는 위치 opt의 범위void solve(int s, int e, int l, int r, int i){ if(l > r) re..

알고리즘/baekjoon 2024. 8. 13. 19:42

첫 번째 조건과 두 번째 조건을 분리하는 것이 포인트이다. 첫 번째 조건에 대한 배열을 만들자.\(MOD[i]\) : \(S\)의 원소를 \(k\)로 나눈 나머지가 \(i\)일때 DP 값의 최댓값두 번째 조건은 DP를 돌리며 세그먼트 트리를 쓸 수 있으므로, 첫 번째 조건과 두 번째 조건에 맞는 최댓값을 구해 \(dp[i]\)를 갱신한다. 그 후 \(MOD[i]\)와 세그먼트 트리를 \(dp[i]\)로 갱신하면 된다.#include using namespace std;typedef long long ll;typedef pair pii;typedef pair pll;typedef tuple tiii;const int MAX = 5*1e5+1;int N, k, d;int S[MAX];int MOD[MAX];..

알고리즘/baekjoon 2024. 7. 16. 18:06

1.길이가 \(k\)인 증가 수열의 개수를 미리 구해 놓으면 길이가 \(k+1\)인 증가 수열의 개수를 쉽게 알 수 있으므로, 이 문제는 DP를 이용해 풀 수 있다. DP 점화식을 다음과 같이 정의하자. \(dp[i][k] = sum(dp[j][k-1]) (j  이 문제를 naive하게 풀면 \(O(N^2)\) 시간복잡도가 나와 TLE를 받을 것이다. 더 좋은 방법이 필요하다. 2.위의 점화식을 풀어 쓰면 \(j \(1\)부터 \(N\)까지 세그먼트 트리에 \(dp[i]\)를 추가하면서, \(dp[1]\)부터 \(dp[A[i]-1]\)까지의 구간합을 구하면 문제를 해결할 수 있다. 또한 \(dp[i][k]\)가 \(dp[i][k-1]\)에만 영향을 미치기 때문에, bottom-up 방식으로 문제를 해결할..

알고리즘/baekjoon 2024. 7. 16. 16:38

1.격자판의 각 칸을 왼쪽 위에서부터 \(0, 1, 2, ... , N*M-1\)이라 하자. 012...                   ...\(K\)xxxxxxx                \(N*M-1\)  \(K\)번 칸 이전은 전부 격자를 채웠다고 가정하고 \(K\)번 칸에 주목해보자. 저 칸에 격자를 놓는 경우는 3가지다. 1. 이미 \(K\)번 격자가 채워져 있어서 격자를 놓을 수 없다.2. 격자를 가로로 놓는다.3. 격자를 세로로 놓는다. 위 세 경우 모두 'x'친 구간에만 영향을 받는다. 따라서 저 'x'친 구간을 하나의 집합으로 관리하며, 집합의 상태에 따라 앞으로 격자를 놓는 경우의 수가 얼마인지 계산해 나가면 문제를 해결할 수 있다. \(K\)번 칸 이후에 격자를 놓을 수 있는 경우..

알고리즘/baekjoon 2024. 6. 28. 19:32

1.소를 K개 이상 연속으로 선택하지 않으면서 최댓값을 만드는 문제이다. 이 문제를 소를 K 이하의 간격으로 선택하면서 최솟값을 만드는 문제로 뒤집어 풀어보자. \(i\)번째 소를 선택했다고 할 때 그 최솟값은 \(i+1, i+2, ... , N\)번째 소를 선택했을 때의 최솟값을 이용해 구할 수 있으므로 이 문제는 DP를 이용해 풀 수 있다. \(dp[i]\) : \(i\)번째 소를 택했을 때의 최솟값 이때 K 이하의 간격으로 소를 택해야 하므로, 점화식은 다음과 같다. \(dp[i] = min(dp[i+1, ... , i+K+1])\) 따라서 우리는 DP table의 구간 최솟값을 구해야 한다. 이는 monotone deque를 이용해 빠르게 구할 수 있다. #include using namespac..

알고리즘/baekjoon 2024. 6. 24. 19:38

1.우리가 \(n-1\)칸까지 타일을 채웠다면, 1칸, 2칸, ... \(n-1\)칸까지 채운 타일의 개수에 대한 정보로 \(n\)칸에 채울 타일의 개수를 DP를 이용해 구할 수 있다. \(dp[i] =  3 * dp[i-1]  + (2 * dp[i-2] + 2 * dp[i-3] + ... + 2 * dp[1])\)\(dp[i+1] = 3 * dp[i]  + 2 * dp[i-1] + (2 * dp[i-2] + ... + 2 * dp[1])\) 괄호 친 부분은 동일하므로, 두 식을 연립하면 다음과 같다. \(dp[i+1] = 4 * dp[i] - dp[i-1]\) 이는 선형 점화식이므로 분할 정복을 이용한 행렬 제곱으로 빠르게 구할 수 있다.이때 행렬에 음수가 포함되어 있으므로, 음수 모듈러 연산에 유의한..

알고리즘/baekjoon 2024. 6. 18. 20:11

1. 나사를 왼쪽으로 돌리면 아래의 모든 나사가 동일하게 왼쪽으로 돌아가며, 오른쪽으로 돌리면 그 나사만 오른쪽으로 돌아간다. 따라서 DP식을 아래와 같이 설정한다. \(dp[i][j]\) : \(i\)번째 나사가 왼쪽으로 \(j\)번 만큼 돌아갔을 때, 원하는 상태로 나사를 돌리는 횟수의 최솟값 이 상태에서 \(i\)번째 나사를 원하는 상태로 만들기 위해 오른쪽으로 돌린 횟수를 \(m\)이라 한다면, 나사를 원하는 상태로 만들기 위해 오른쪽으로 돌렸을 때의 최솟값은 다음과 같다.\(dp[i+1][j] + m\) 왼쪽으로 돌린 횟수는 그 반대인  \(10 - m\)이 된다. 나사를 원하는 상태로 만들기 위해 왼쪽으로 돌렸을 때의 최솟값은 다음과 같다.\(dp[i+1][j+10-m] + (10 - m)\)..

알고리즘/baekjoon 2024. 6. 18. 12:28