목차
- 백준 4933 - 마스터 (선형 DP)
- 백준 5858 - 황금 검 (선형 DP)
- 백준 1280 - 닉의 임무 (선형 DP)
- USACO 2016 오픈 - 2048 (구간 DP)
- 백준 2585 - 삼색 이진 트리 (트리 DP)
- 백준 1441 - 추 저울질 (조합 탐색 + 배낭)
- 백준 1896 - 서로 공격하지 않음 (비트마스크 DP)
- Codeforces 1488E - 회문 쌍 (LIS 응용)
- Codeforces 1486D - 최대 중앙값 (이분 탐색)
- Codeforces 1486E - 쌍대 지불 (다차원 최단 경로)
- Codeforces 1426F - 부분 수열의 개수 (카운팅 DP)
백준 4933 - 마스터
문제: 길이 n인 수열 h가 주어질 때, 등차수열을 이루는 부분 수열의 개수를 구하라. (n < 1e3, h[i] < 2e4)
풀이: n과 h[i]의 범위를 고려하여 dp[i][j]를 i번째 원소를 마지막으로 하고 공차가 j인 등차수열의 개수로 정의한다. 이중 반복문으로 이전 원소를 순회하며 값을 갱신한다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;
const int MAXH = 20005;
int h[1005];
int dp[1005][3 * MAXH];
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n; cin >> n;
for (int i = 1; i <= n; i++) cin >> h[i];
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
int diff = h[i] - h[j] + MAXH;
dp[i][diff] = (dp[i][diff] + dp[j][diff] + 1) % MOD;
ans = (ans + dp[j][diff] + 1) % MOD;
}
}
ans = (ans + n) % MOD;
cout << ans << '\n';
return 0;
}
백준 5858 - 황금 검
문제: n개의 재료를 순서대로 용기에 넣는다. 용량은 w이며, 재료를 넣기 전에 최대 s개를 꺼낼 수 있다. 넣을 때 점수 = (현재 용기 속 재료 개수) * (재료 가중치)를 얻는다. 총 점수의 최댓값을 구하라. (n, w, s < 5e5)
풀이: dp[i][j]를 i번째 재료까지 처리하고 용기에 j개가 있을 때의 최대 점수로 정의한다. 전이는 j-1부터 j+s-1 범위의 최댓값을 필요로 하므로, 슬라이딩 윈도우 최댓값(덱)을 사용하여 O(1)에 처리한다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
const int N = 5005;
ll a[N], dp[N][N];
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
ll n, w, s; cin >> n >> w >> s;
for (int i = 1; i <= n; i++) cin >> a[i];
dp[1][1] = a[1];
for (int i = 2; i <= n; i++) {
deque<int> dq;
if (i > w) dq.push_back(w);
for (int j = min((ll)i, w); j >= 1; j--) {
if (j > 1) {
while (!dq.empty() && dp[i-1][dq.back()] <= dp[i-1][j-1]) dq.pop_back();
dq.push_back(j-1);
}
while (!dq.empty() && dq.front() > j-1+s) dq.pop_front();
dp[i][j] = dp[i-1][dq.empty() ? 0 : dq.front()] + a[i] * j;
}
}
ll ans = -INF;
for (int j = 1; j <= min(n, w); j++) ans = max(ans, dp[n][j]);
cout << ans << '\n';
return 0;
}
백준 1280 - 닉의 임무
문제: n시간 동안 m개의 임무가 있다. 각 임무는 시작 시간과 지속 시간이 주어진다. 현재 시간에 시작하는 임무가 있으면 반드시 하나를 선택해야 한다. 가장 긴 여유 시간을 구하라.
풀이: dp[i]를 i초부터 n초까지의 최대 여유 시간으로 정의하고, 역방향으로 순회한다. i초에 시작하는 임무가 없다면 dp[i] = dp[i+1] + 1, 있다면 dp[i] = max(dp[i], dp[i + 지속시간])을 계산한다.
#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
vector<int> tasks[N];
int dp[N];
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m; cin >> n >> m;
for (int i = 0; i < m; i++) {
int s, t; cin >> s >> t;
tasks[s].push_back(t);
}
for (int i = n; i >= 1; i--) {
if (tasks[i].empty()) {
dp[i] = dp[i+1] + 1;
} else {
for (int t : tasks[i]) {
dp[i] = max(dp[i], dp[i + t]);
}
}
}
cout << dp[1] << '\n';
return 0;
}
USACO 2016 오픈 - 2048
문제: n개의 숫자로 구성된 수열이 있다. 인접한 두 값이 같으면 하나로 합쳐지고 값이 1 증가한다. 최종적으로 만들 수 있는 가장 큰 수를 구하라.
풀이: dp[L][R]을 구간 [L, R]이 합쳐져서 만들어진 수로 정의한다. 합쳐질 수 없으면 0이다. 중간 지점 k를 기준으로 dp[L][k]와 dp[k+1][R]이 같고 0이 아니면 dp[L][R] = dp[L][k] + 1이 된다.
#include <bits/stdc++.h>
using namespace std;
const int N = 256;
int dp[N][N];
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n; cin >> n;
int ans = 0;
for (int i = 1; i <= n; i++) {
cin >> dp[i][i];
ans = max(ans, dp[i][i]);
}
for (int len = 2; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
for (int k = l; k < r; k++) {
if (dp[l][k] && dp[k+1][r] && dp[l][k] == dp[k+1][r]) {
dp[l][r] = dp[l][k] + 1;
ans = max(ans, dp[l][r]);
}
}
}
}
cout << ans << '\n';
return 0;
}
백준 2585 - 삼색 이진 트리
문제: 이진 트리의 각 노드를 빨강, 초록, 파랑으로 칠한다. 부모-자식, 형제 간은 색이 달라야 한다. 초록색 노드의 최대 개수와 최소 개수를 구하라. (n < 5e5)
풀이: 트리 DP로 dp_max[node][0/1]은 노드가 초록이 아닐 때/초록일 때 서브트리의 최대 초록 개수, dp_min도 유사하게 정의한다. 자식이 0, 1, 2개인 경우를 나누어 전이시킨다.
#include <bits/stdc++.h>
using namespace std;
const int N = 550010;
char t[N];
int f[N][2], g[N][2], sz[N];
void dfs(int x) {
f[x][0] = 0; f[x][1] = 1;
g[x][0] = 0; g[x][1] = 1;
sz[x] = 0;
int child[3] = {0};
int cnt = t[x] - '0';
for (int i = 1; i <= cnt; i++) {
int y = x + sz[x] + 1;
child[i] = y;
dfs(y);
sz[x] += sz[y];
}
sz[x] += 1;
if (cnt == 0) return;
if (cnt == 1) {
f[x][0] += max(f[child[1]][0], f[child[1]][1]);
f[x][1] += f[child[1]][0];
g[x][0] += min(g[child[1]][0], g[child[1]][1]);
g[x][1] += g[child[1]][0];
} else {
f[x][0] += max(f[child[1]][0] + f[child[2]][1], f[child[1]][1] + f[child[2]][0]);
f[x][1] += f[child[1]][0] + f[child[2]][0];
g[x][0] += min(g[child[1]][0] + g[child[2]][1], g[child[1]][1] + g[child[2]][0]);
g[x][1] += g[child[1]][0] + g[child[2]][0];
}
}
int main() {
cin >> t;
dfs(0);
cout << max(f[0][0], f[0][1]) << ' ' << min(g[0][0], g[0][1]) << '\n';
return 0;
}
백준 1441 - 추 저울질
문제: n개의 추 중에서 n-m개를 선택하여, 1g 단위로 몇 개의 무게를 측정할 수 있는지 최댓값을 구하라. (n <= 20, m <= 4)
풀이: 조합으로 버릴 m개의 추를 선택하고, 남은 추로 01 배낭 DP를 수행하여 측정 가능한 무게 개수를 센다. 최대값을 갱신한다.
#include <bits/stdc++.h>
using namespace std;
int a[23], sel[23], n, m, ans;
bool dp[2030];
void calc() {
fill(dp, dp+2030, false);
dp[0] = true;
int sum = 0, cnt = 0;
for (int i = 1; i <= n; i++) {
if (sel[i]) continue;
for (int j = sum; j >= 0; j--) {
if (dp[j] && !dp[j + a[i]]) {
dp[j + a[i]] = true;
cnt++;
}
}
sum += a[i];
}
ans = max(ans, cnt);
}
void dfs(int idx, int removed) {
if (removed == m) { calc(); return; }
for (int i = idx + 1; i <= n - m + removed + 1; i++) {
sel[i] = 1;
dfs(i, removed + 1);
sel[i] = 0;
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
dfs(0, 0);
cout << ans << '\n';
return 0;
}
백준 1896 - 서로 공격하지 않음
문제: n×n 체스판에 m개의 왕을 배치한다. 왕은 8방향으로 한 칸 내에 있는 다른 왕을 공격할 수 있다. 서로 공격하지 않도록 배치하는 경우의 수를 구하라. (n <= 9)
풀이: dp[i][j][state]를 i행까지 j개의 왕을 배치하고 마지막 행의 상태가 state일 때 경우의 수로 정의한다. 미리 한 행에 가능한 상태(인접 1이 없는)와 각 상태의 왕 개수를 저장하고, 행 간 충돌 여부를 비트 연산으로 확인하여 전이한다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll dp[10][100][550];
vector<pair<int,int>> states;
int bitcnt(int x) {
int c = 0;
while (x) { c++; x &= x-1; }
return c;
}
bool valid_row(int x) {
return !(x & (x >> 1));
}
bool compatible(int a, int b) {
if (a & b) return false;
if (a & (b << 1)) return false;
if (a & (b >> 1)) return false;
return true;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m; cin >> n >> m;
int total = 1 << n;
for (int i = 0; i < total; i++) {
if (valid_row(i)) states.push_back({i, bitcnt(i)});
}
dp[0][0][0] = 1;
ll ans = 0;
for (int i = 1; i <= n; i++) {
int maxk = min(m, ((n+1)/2) * ((i+1)/2));
for (int j = 0; j <= maxk; j++) {
if (j == 0) { dp[i][0][0] = 1; continue; }
for (auto [cur, c_cnt] : states) {
if (c_cnt > j) continue;
for (auto [prev, _] : states) {
if (!compatible(cur, prev)) continue;
dp[i][j][cur] += dp[i-1][j - c_cnt][prev];
}
}
}
if (i == n) {
for (auto [cur, _] : states) ans += dp[n][m][cur];
}
}
cout << ans << '\n';
return 0;
}
Codeforces 1488E - 회문 쌍
문제: 각 숫자가 최대 두 번 등장하는 수열에서 가장 긴 회문 부분 수열의 길이를 구하라.
풀이: 짝수 길이 회문은 같은 숫자 쌍으로 구성된다. 첫 번째 등장 위치를 기준으로 정렬하고, 두 번째 등장 위치의 LIS를 구하면 2*LIS가 짝수 길이 최댓값이다. 홀수 길이 회문이 가능한지 확인하려면 LIS의 한 원소에서 첫 번째와 두 번째 위치 사이에 공백이 있는지 체크한다.
#include <bits/stdc++.h>
using namespace std;
const int N = 255000;
int a[N];
pair<int,int> p[N];
int LIS[N], dp[N];
void solve() {
int n; cin >> n;
for (int i = 1; i <= n; i++) p[i] = {0, 0};
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (p[a[i]].first == 0) p[a[i]].first = i;
else p[a[i]].second = i;
}
vector<pair<int,int>> vec;
for (int i = 1; i <= n; i++) {
if (p[i].second != 0) vec.push_back({p[i].first, p[i].second});
}
if (vec.empty()) { cout << 1 << '\n'; return; }
sort(vec.begin(), vec.end(), [](auto &a, auto &b) { return a.first > b.first; });
int len = 0, ans = 0;
for (int i = 0; i < vec.size(); i++) {
int idx = upper_bound(dp, dp + len, vec[i].second) - dp;
dp[idx] = vec[i].second;
LIS[i] = idx + 1;
if (idx == len) len++;
}
vector<int> max_at_len(len + 1, 0);
vector<bool> used(vec.size(), false);
for (int i = vec.size()-1; i >= 0; i--) {
if (LIS[i] == len) {
max_at_len[len] = max(max_at_len[len], vec[i].second);
used[i] = true;
} else if (vec[i].second < max_at_len[LIS[i]+1]) {
max_at_len[LIS[i]] = max(max_at_len[LIS[i]], vec[i].second);
used[i] = true;
}
}
bool odd_possible = false;
for (int i = 0; i < vec.size(); i++) {
if (LIS[i] == 1 && used[i] && (vec[i].second - vec[i].first > 1)) {
odd_possible = true;
break;
}
}
ans = 2 * len;
if (odd_possible) ans++;
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int t; cin >> t;
while (t--) solve();
return 0;
}
Codeforces 1486D - 최대 중앙값
문제: 길이 n인 배열에서 길이가 k 이상인 모든 연속 부분 배열의 중앙값 중 최댓값을 구하라.
풀이: 이분 탐색으로 답 x를 가정한다. 배열에서 x 이상은 1, 미만은 -1로 치환하고, 길이가 k 이상인 구간의 합이 1 이상인지 확인한다. 최소 prefix 합을 유지하며 슬라이딩 윈도우로 검사한다.
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int a[N], b[N];
bool check(int x, int n, int k) {
for (int i = 1; i <= n; i++) b[i] = (a[i] >= x) ? 1 : -1;
int sum = 0, mn = 0, pre = 0;
for (int i = 1; i <= k; i++) sum += b[i];
if (sum >= 1) return true;
for (int i = k+1; i <= n; i++) {
sum += b[i];
pre += b[i-k];
mn = min(mn, pre);
if (sum - mn >= 1) return true;
}
return false;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, k; cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
int lo = 1, hi = n;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (check(mid, n, k)) lo = mid;
else hi = mid - 1;
}
cout << lo << '\n';
return 0;
}
Codeforces 1486E - 쌍대 지불
문제: 무방향 가중치 그래프에서 이동은 항상 연속된 두 간선을 한 번에 사용하며, 비용은 (w1 + w2)^2이다. 1번 정점에서 각 정점까지의 최단 거리를 구하라.
풀이: dis[u][w][parity]를 u 정점에 도착했고, 마지막 간선의 가중치가 w이며, 현재가 짝수/홀수 번째 간선인 상태의 최단 거리로 정의한다. 다익스트라를 확장하여 상태 전이를 수행한다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100005;
const ll INF = 1e18;
vector<pair<int,int>> g[N];
ll dis[N][51][2];
struct Node {
ll d; int last, odd, v;
bool operator&g;(const Node &o) const { return d > o.d; }
};
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m; cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, w; cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
for (int i = 1; i <= n; i++)
for (int j = 0; j <= 50; j++)
dis[i][j][0] = dis[i][j][1] = INF;
priority_queue<Node> pq;
dis[1][0][0] = 0;
pq.push({0, 0, 0, 1});
while (!pq.empty()) {
auto [d, last, odd, u] = pq.top(); pq.pop();
if (d != dis[u][last][odd]) continue;
for (auto [v, w] : g[u]) {
if (odd) {
ll nd = d + (last + w) * (last + w);
if (nd < dis[v][w][0]) {
dis[v][w][0] = nd;
pq.push({nd, w, 0, v});
}
} else {
if (d < dis[v][w][1]) {
dis[v][w][1] = d;
pq.push({d, w, 1, v});
}
}
}
}
for (int i = 1; i <= n; i++) {
ll ans = INF;
for (int j = 0; j <= 50; j++) ans = min(ans, dis[i][j][0]);
cout << (ans == INF ? -1 : ans) << ' ';
}
cout << '\n';
return 0;
}
Codeforces 1426F - 부분 수열의 개수
문제: 'a', 'b', 'c', '?'로 이루어진 문자열이 주어진다. '?'는 'a', 'b', 'c' 중 하나로 바뀔 수 있다. 가능한 모든 문자열에서 "abc" 부분 수열의 총 개수를 구하라.
풀이: dp[0], dp[1], dp[2], dp[3]을 각각 빈 문자열, "a", "ab", "abc"의 개수로 정의한다. '?'가 나오면 모든 경우를 3배로 확장하며 점화식을 업데이트한다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9+7;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n; string s; cin >> n >> s;
ll dp[4] = {1, 0, 0, 0};
for (char c : s) {
if (c == 'a') dp[1] = (dp[1] + dp[0]) % MOD;
else if (c == 'b') dp[2] = (dp[2] + dp[1]) % MOD;
else if (c == 'c') dp[3] = (dp[3] + dp[2]) % MOD;
else {
dp[3] = (3 * dp[3] + dp[2]) % MOD;
dp[2] = (3 * dp[2] + dp[1]) % MOD;
dp[1] = (3 * dp[1] + dp[0]) % MOD;
dp[0] = (3 * dp[0]) % MOD;
}
}
cout << dp[3] << '\n';
return 0;
}