A. 배증(Binary Lifting)을 활용한 교대 운전 경로 최적화
두 운전자가 정해진 규칙에 따라 번갈아가며 차량을 운전합니다. A는 진행 방향에서 두 번째로 가까운 도시로 이동하고, B는 가장 가까운 도시로 이동합니다. 출발 도시와 최대 주행 거리 제한이 주어졌을 때, A의 주행 거리 대 B의 주행 거리 비가 최소가 되는 출발 도시를 찾고, 특정 출발점과 거리 제한에 따른 각자의 주행 거리를 구하는 문제입니다.
해결 전략은 각 도시에서 다음으로 이동할 도시와 해당 구간 거리를 전처리한 후, 배증 기법을 적용하는 것입니다. 도시의 수평 위치 관계는 높낮이 정보로 결정되므로, 역순으로 순회하며 정렬된 자료구조를 활용하여 각 도시에서 가장 가깝고 두 번째로 가까운 도시를 선별합니다. 이후 2의 거듭제곱 단계별 이동 정보를 기록하는 상태 배열을 구성합니다. 쿼리 처리 시에는 높은 비트부터 순차적으로 확인하며 총 이동 거리가 제한을 넘지 않도록 점진적으로 상태를 누적하면 됩니다.
#include <iostream>
#include <cstdio>
#include <set>
#include <algorithm>
#include <cmath>
using namespace std;
using ll = long long;
const int MAXN = 100005;
const ll INF_DIST = 4e18;
struct Location {
int idx;
ll alt;
bool operator<(const Location& o) const {
return alt < o.alt;
}
};
int n, q_cnt;
Location loc[MAXN];
int nxt_city[20][MAXN][2];
ll distA[20][MAXN][2], distB[20][MAXN][2];
multiset<Location> sorted_locs;
pair<ll, ll> simulate(int start, ll limit) {
int curr = start;
ll a_run = 0, b_run = 0;
for (int k = 19; k >= 0; --k) {
if (nxt_city[k][curr][0] != 0 && a_run + b_run + distA[k][curr][0] + distB[k][curr][0] <= limit) {
a_run += distA[k][curr][0];
b_run += distB[k][curr][0];
curr = nxt_city[k][curr][0];
}
}
return {a_run, b_run};
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &loc[i].alt);
loc[i].idx = i;
}
sorted_locs.insert({0, INF_DIST});
sorted_locs.insert({n + 1, -INF_DIST});
for (int i = n; i >= 1; --i) {
auto it = sorted_locs.insert(loc[i]);
auto it_fwd = it; ++it_fwd; ++it_fwd;
auto it_bwd = it; --it_bwd; --it_bwd; --it_bwd; --it_bwd;
pair<int, ll> candidates[4] = {
{(*it_fwd).idx, (*it_fwd).alt - loc[i].alt},
{(*it_fwd).idx, (*it_fwd).alt - loc[i].alt},
{(*it_bwd).idx, loc[i].alt - (*it_bwd).alt},
{(*it_bwd).idx, loc[i].alt - (*it_bwd).alt}
};
sort(candidates, candidates + 4, [](const pair<int,ll>& a, const pair<int,ll>& b){
if (a.second != b.second) return a.second < b.second;
return loc[a.first].alt < loc[b.first].alt;
});
int first = candidates[0].first, second = candidates[1].first;
nxt_city[0][i][0] = second;
nxt_city[0][i][1] = first;
distA[0][i][0] = abs(loc[i].alt - loc[second].alt);
distB[0][i][1] = abs(loc[i].alt - loc[first].alt);
}
for (int j = 1; j <= n; ++j) {
for (int driver = 0; driver < 2; ++driver) {
int mid = nxt_city[0][j][driver];
nxt_city[1][j][driver] = nxt_city[0][mid][driver ^ 1];
distA[1][j][driver] = distA[0][j][driver] + distA[0][mid][driver ^ 1];
distB[1][j][driver] = distB[0][j][driver] + distB[0][mid][driver ^ 1];
}
}
int max_log = log2(n);
for (int k = 2; k <= max_log; ++k) {
for (int j = 1; j <= n; ++j) {
for (int driver = 0; driver < 2; ++driver) {
int mid = nxt_city[k-1][j][driver];
nxt_city[k][j][driver] = nxt_city[k-1][mid][driver];
distA[k][j][driver] = distA[k-1][j][driver] + distA[k-1][mid][driver];
distB[k][j][driver] = distB[k-1][j][driver] + distB[k-1][mid][driver];
}
}
}
ll limit;
scanf("%lld", &limit);
int best_start = 1;
double min_ratio = 1e18;
for (int i = 1; i <= n; ++i) {
auto [a_dist, b_dist] = simulate(i, limit);
double ratio = (b_dist == 0) ? 1e18 : (double)a_dist / b_dist;
if (ratio < min_ratio - 1e-9 || (abs(ratio - min_ratio) < 1e-9 && loc[i].alt > loc[best_start].alt)) {
min_ratio = ratio;
best_start = i;
}
}
printf("%d\n", best_start);
scanf("%d", &q_cnt);
while (q_cnt--) {
int s; ll x;
scanf("%d%lld", &s, &x);
auto [a, b] = simulate(s, x);
printf("%lld %lld\n", a, b);
}
return 0;
}B. 문자열 반복 횟수 최대화 (배증 DP)
두 문자열과 각각의 반복 횟수가 주어집니다. 두 번째 문자열을 특정 횟수만큼 반복한 결과가 첫 번째 문자열을 반복한 결과의 부분수열이 될 수 있을 때, 가능한 최대 반복 배수를 구하는 문제입니다.
문자열 매칭 과정을 배증 방식으로 가속화할 수 있습니다. 시작 인덱스와 2의 거듭제곱 단계에 대해, 목표 문자열을 형성하는 데 필요한 최소 길이 배열을 구성합니다. 초기값은 단순 순회로 매칭하며, 이후 각 단계에서 이전 단계 두 번 분량을 합산하는 방식으로 상태 전이합니다. 구배가 높은 비트부터 확인하며 전체 길이 제한 내에서 최대한 많은 구간을 누적하면 정답을 도출할 수 있습니다.
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXL = 105;
int req_len[MAXL][20];
string strA, strB;
int nA, nB, lenA, lenB, max_pow;
int main() {
while (cin >> strB >> nB >> strA >> nA) {
lenA = strA.size();
lenB = strB.size();
max_pow = (int)log2((lenA * nA) / lenB);
for (int i = 0; i < lenA; ++i) {
int ptr = i;
req_len[i][0] = 0;
for (char ch : strB) {
int steps = 0;
while (strA[ptr] != ch) {
ptr = (ptr + 1) % lenA;
steps++;
if (steps > lenA) goto next_case;
}
req_len[i][0] += steps + 1;
ptr = (ptr + 1) % lenA;
}
}
for (int j = 1; j <= max_pow; ++j) {
for (int i = 0; i < lenA; ++i) {
int mid = req_len[i][j-1];
req_len[i][j] = mid + req_len[(i + mid) % lenA][j-1];
}
}
int consumed = 0;
long long total_rep = 0;
for (int j = max_pow; j >= 0; --j) {
int needed = req_len[consumed % lenA][j];
if (consumed + needed <= lenA * nA) {
consumed += needed;
total_rep += (1LL << j);
}
}
cout << total_rep / nB << '\n';
next_case: continue;
}
return 0;
}C. 작업 구간 최소 덮개 수 (세그먼트 트리 최적화)
주어진 여러 구간에 최소한의 개수를 선택하여 연속된 범위 `[1, T]`를 모두 덮는 문제입니다. 각 구간은 `[l, r]` 형식으로 주어지며 중복은 허용됩니다.
구간을 끝점 기준으로 정렬한 후, 동적 계획법을 적용합니다. `dp[i]`는 `[1, i]` 범위를 덮는 최소 구간 수로 정의합니다. 상태 전이 시 `dp[r] = min(dp[l-1 ... r-1]) + 1` 형태가 되므로, 구간 최솟값 쿼리를 효율적으로 처리하기 위해 세그먼트 트리를 도입합니다. 좌표 범위가 넓을 경우 좌표 압축을 병행하여 메모리 사용량을 최적화합니다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 25005;
const int INF = 0x3f3f3f3f;
struct Interval { int l, r; };
Interval intervals[MAXN];
int coord[4 * MAXN];
int dp[MAXN * 4];
int tree_min[4 * MAXN * 4];
void update(int node, int start, int end, int idx, int val) {
if (start == end) { tree_min[node] = val; return; }
int mid = (start + end) / 2;
if (idx <= mid) update(2*node, start, mid, idx, val);
else update(2*node+1, mid+1, end, idx, val);
tree_min[node] = min(tree_min[2*node], tree_min[2*node+1]);
}
int query(int node, int start, int end, int l, int r) {
if (r < start || end < l) return INF;
if (l <= start && end <= r) return tree_min[node];
int mid = (start + end) / 2;
return min(query(2*node, start, mid, l, r),
query(2*node+1, mid+1, end, l, r));
}
int main() {
int n, T;
scanf("%d%d", &n, &T);
int c_cnt = 1;
coord[c_cnt++] = 1;
coord[c_cnt++] = T;
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &intervals[i].l, &intervals[i].r);
coord[c_cnt++] = intervals[i].l;
coord[c_cnt++] = intervals[i].r;
coord[c_cnt++] = intervals[i].l + 1;
coord[c_cnt++] = intervals[i].r + 1;
}
sort(coord + 1, coord + c_cnt);
c_cnt = unique(coord + 1, coord + c_cnt) - coord - 1;
while (coord[c_cnt] > T) c_cnt--;
sort(intervals + 1, intervals + n + 1, [](const Interval& a, const Interval& b){
return a.r < b.r;
});
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
memset(tree_min, 0x3f, sizeof(tree_min));
update(1, 0, c_cnt, 0, 0);
for (int i = 1; i <= n; ++i) {
int L = lower_bound(coord, coord + c_cnt + 1, intervals[i].l) - coord;
int R = lower_bound(coord, coord + c_cnt + 1, intervals[i].r) - coord;
int best = query(1, 0, c_cnt, L-1, R-1) + 1;
if (dp[R] > best) {
dp[R] = best;
update(1, 0, c_cnt, R, best);
}
}
int ans = dp[lower_bound(coord, coord + c_cnt + 1, T) - coord];
printf("%d\n", ans == INF ? -1 : ans);
return 0;
}D. 가중치 구간 최소 비용 덮개
각 구간에 비용이 부여된 경우, 지정된 범위 `[L, R]`를 덮는 최소 총 비용을 구하는 문제입니다. 중복 덮개가 허용되며, 범위 외부 구간은 무시됩니다.
이전 문제와 구조가 유사하지만, 각 구간 선택 시 비용이 누적되고 목표 범위가 `[L, R]`로 명시되어 있습니다. `dp[i]`를 `[L, i]`를 덮는 최소 비용으로 정의하면, `dp[r] = min(dp[l-1 ... r-1]) + cost` 형태의 전이가 발생합니다. 좌표 범위가 86,400 이내이므로 직접 인덱싱이 가능하며, 세그먼트 트리를 활용한 구간 최솟값 조회로 효율성을 확보합니다.
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 10005;
const int MAXR = 86405;
const long long INF_COST = 4e18;
struct Task { int l, r, w; };
Task tasks[MAXN];
long long tree_val[MAXR * 4];
long long dp[MAXR];
void update(int node, int start, int end, int idx, long long val) {
if (start == end) { tree_val[node] = val; return; }
int mid = (start + end) / 2;
if (idx <= mid) update(2*node, start, mid, idx, val);
else update(2*node+1, mid+1, end, idx, val);
tree_val[node] = min(tree_val[2*node], tree_val[2*node+1]);
}
long long query(int node, int start, int end, int l, int r) {
if (r < start || end < l) return INF_COST;
if (l <= start && end <= r) return tree_val[node];
int mid = (start + end) / 2;
return min(query(2*node, start, mid, l, r),
query(2*node+1, mid+1, end, l, r));
}
int main() {
int n, L, R;
scanf("%d%d%d", &n, &L, &R);
for (int i = 1; i <= n; ++i) {
scanf("%d%d%d", &tasks[i].l, &tasks[i].r, &tasks[i].w);
tasks[i].l = max(tasks[i].l, L);
tasks[i].r = min(tasks[i].r, R);
}
sort(tasks + 1, tasks + n + 1, [](const Task& a, const Task& b){
return a.r < b.r;
});
memset(tree_val, 0x3f, sizeof(tree_val));
memset(dp, 0x3f, sizeof(dp));
dp[L] = 0;
update(1, L, R, L, 0);
for (int i = 1; i <= n; ++i) {
if (tasks[i].l > tasks[i].r) continue;
long long prev_min = query(1, L, R, tasks[i].l, tasks[i].r);
long long new_cost = prev_min + tasks[i].w;
if (new_cost < dp[tasks[i].r]) {
dp[tasks[i].r] = new_cost;
update(1, L, R, tasks[i].r, new_cost);
}
}
printf("%lld\n", dp[R] >= INF_COST ? -1 : dp[R]);
return 0;
}E. 길이 M인 strictly 증가 부분수열 개수 (BIT 최적화)
주어진 수열에서 길이 `m`인嚴格遞增(Strictly Increasing) 부분수열의 개수를 구하는 문제입니다. 여러 테스트 케이스가 주어지며 답은 `1e9+7`으로 나눈 나머지입니다.
`dp[len][i]`를 길이 `len`이고 `i`번 요소를 마지막으로 하는 부분수열의 개수로 정의합니다. 전이 식은 `dp[len][i] = sum(dp[len-1][j])` (j < i 이고 A[j] < A[i]) 형태입니다. 내포 반복문은 시간 초과를 유발하므로, BIT(Binary Indexed Tree)를 도입하여 값 기준의 접두합을 관리합니다. 좌표 압축을 통해 큰 숫자를 작은 인덱스로 매핑한 후, 길이별로 순차적으로 BIT를 갱신하며 계산합니다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 1005;
const int MOD = 1e9 + 7;
int bit[MAXN];
int ways[MAXN][MAXN];
int raw[MAXN], vals[MAXN];
int n, m, uniq_cnt;
void add(int idx, int val) {
for (; idx <= uniq_cnt; idx += idx & -idx) {
bit[idx] = (bit[idx] + val) % MOD;
}
}
int ask(int idx) {
int res = 0;
for (; idx > 0; idx -= idx & -idx) {
res = (res + bit[idx]) % MOD;
}
return res;
}
int main() {
int T;
scanf("%d", &T);
for (int tc = 1; tc <= T; ++tc) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", &raw[i]);
sort(raw + 1, raw + n + 1);
uniq_cnt = unique(raw + 1, raw + n + 1) - (raw + 1);
for (int i = 1; i <= n; ++i) {
vals[i] = lower_bound(raw + 1, raw + uniq_cnt + 1, raw[i]) - raw;
}
memset(ways, 0, sizeof(ways));
for (int len = 1; len <= m; ++len) {
memset(bit, 0, sizeof(bit));
for (int i = 1; i <= n; ++i) {
int cnt = ask(vals[i] - 1);
ways[len][i] = cnt;
if (len == 1) cnt = 1;
add(vals[i], (len == 1) ? 1 : ways[len-1][i]);
}
}
long long total = 0;
for (int i = 1; i <= n; ++i) {
total = (total + ways[m][i]) % MOD;
}
printf("Case #%d: %lld\n", tc, total);
}
return 0;
}F. 수열 분할 최소 개수 (단조 큐 최적화)
원본 자료에 상세 해설이 누락되어 있으나, 단조 큐(Monotonic Queue)를 활용한 DP 최적화 기법의 전형적인 예제입니다. 일반적으로 연속 구간의 합이 일정 기준을 넘지 않도록 분할할 때, 유효한 이전 상태 후보들만 큐에 유지하며 선형 시간에 전이를 수행합니다.
G. 서브트리 선택 최소 비용 (트리 DP)
림 또는 트리 구조에서 각 노점을 선택할 때 비용이 발생하며, 노드를 선택하면 해당 서브트리의 전체 크기가 가치로 인정됩니다. 최소 `m`의 가치를 얻기 위한 최소 비용의 합을 구합니다.
트리를 상향식으로 순회하며 각 서브트리의 가치와 비용 관계를 기록합니다. `cost[u][v]`는 `u`를 루트로 하는 서브트리에서 가치 `v`를 확보하는 최소 비용입니다. 자녀 노드를 병합할 때는 배낭 문제(Knapsack)와 유사하게 역순으로 순회하여 상태 충돌을 방지합니다. 루트 선택 시에는 서브트리 전체 크기를 가치로, 해당 노드 비용을 값으로 갱신하며 최솟값을 유지합니다. 다수의 루트가 있는 경우 인공 루트를 추가하여 통합 처리합니다.
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int MAXN = 205;
const int INF = 0x3f3f3f3f;
int node_cost[MAXN], subtree_sz[MAXN], dp_cost[MAXN][MAXN];
vector<int> adj[MAXN];
int n, target;
unordered_map<string, int> name_to_id;
bool is_root[MAXN];
int dfs(int u) {
fill(dp_cost[u], dp_cost[u] + MAXN, INF);
dp_cost[u][0] = 0;
int cur_sz = 1;
for (int v : adj[u]) {
cur_sz += dfs(v);
for (int i = n; i >= 0; --i) {
for (int j = 0; j <= i; ++j) {
dp_cost[u][i] = min(dp_cost[u][i], dp_cost[u][i-j] + dp_cost[v][j]);
}
}
}
dp_cost[u][cur_sz] = min(dp_cost[u][cur_sz], node_cost[u]);
subtree_sz[u] = cur_sz;
return cur_sz;
}
int main() {
int id_counter = 0;
while (true) {
string line;
getline(cin, line);
if (line.empty() || line[0] == '#') break;
sscanf(line.c_str(), "%d%d", &n, &target);
id_counter = 0;
name_to_id.clear();
fill(is_root, is_root + MAXN, true);
for (int i = 0; i <= n; ++i) adj[i].clear();
for (int i = 0; i < n; ++i) {
string name;
int val;
cin >> name >> val;
if (!name_to_id.count(name)) name_to_id[name] = ++id_counter;
int u = name_to_id[name];
node_cost[u] = val;
string child;
while (cin >> child && !child.empty() && child.back() != '\r' && child.back() != '\n') {
if (!name_to_id.count(child)) name_to_id[child] = ++id_counter;
int v = name_to_id[child];
is_root[v] = false;
adj[u].push_back(v);
}
}
for (int i = 1; i <= n; ++i) {
if (is_root[i]) adj[0].push_back(i);
}
node_cost[0] = INF;
dfs(0);
int ans = INF;
for (int i = target; i <= n; ++i) ans = min(ans, dp_cost[0][i]);
printf("%d\n", ans);
}
return 0;
}H. 각 노드 기준 최장 경로 (재루팅 트리 DP)
가중치 트리가 주어졌을 때, 각 노드를 시작점으로 하여 다른 모든 노드까지 가는 최대 거리 중 최댓값을 구하는 문제입니다.
하나의 DFS로는 하향 경로만 처리할 수 있으므로, 재루팅 기법을 적용합니다. 첫 번째 DFS에서 각 노드의 하위 서브트리를 향한 최장 경로(`down1`)와 차장 경로(`down2`)를 기록합니다. 두 번째 DFS에서는 상위 노드 정보를 활용하여 상향 최장 경로(`up`)를 계산합니다. 하향 최장 경로가 현재 자식 경로를 통해 지나갔다면, 상향 계산 시 차장 경로값을 대신 참조하여 경로 중복을 방지합니다. 최종 답은 각 노드 기준 `max(down1, up)`입니다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 100005;
struct Edge { int to, weight; };
vector<Edge> graph[MAXN];
int down_max[MAXN][2]; // [0]: 1st max, [1]: 2nd max
int up_max[MAXN];
int max_child[MAXN];
int n;
void compute_down(int u, int parent) {
down_max[u][0] = down_max[u][1] = 0;
max_child[u] = -1;
for (auto& e : graph[u]) {
if (e.to == parent) continue;
compute_down(e.to, u);
int val = down_max[e.to][0] + e.weight;
if (val > down_max[u][0]) {
down_max[u][1] = down_max[u][0];
down_max[u][0] = val;
max_child[u] = e.to;
} else if (val > down_max[u][1]) {
down_max[u][1] = val;
}
}
}
void compute_up(int u, int parent) {
for (auto& e : graph[u]) {
if (e.to == parent) continue;
int alt = (max_child[u] == e.to) ? down_max[u][1] : down_max[u][0];
up_max[e.to] = max(up_max[u], alt) + e.weight;
compute_up(e.to, u);
}
}
int main() {
while (scanf("%d", &n) == 1) {
for (int i = 1; i <= n; ++i) {
graph[i].clear();
down_max[i][0] = down_max[i][1] = up_max[i] = 0;
}
for (int i = 2; i <= n; ++i) {
int p, w;
scanf("%d%d", &p, &w);
graph[i].push_back({p, w});
graph[p].push_back({i, w});
}
compute_down(1, -1);
up_max[1] = 0;
compute_up(1, -1);
for (int i = 1; i <= n; ++i) {
printf("%d\n", max(down_max[i][0], up_max[i]));
}
}
return 0;
}I. XOR 경로 기대값 (순환 의존성 및 선형방정식)
원본 자료에 상세 해설이 준비 중입니다. 일반적으로 그래프상에서의 랜덤 워크 기대값 문제는 상태 간 순환 의존성을 가우스 소거법(Gaussian Elimination)을 통해 해결합니다.
J. 펜스 장애물 최소화 (세그먼트 트리 구간 매핑)
수평으로 배치된 여러 펜스를 지나 출발점에서 종단점을 이동할 때, 수평 이동 거리를 최소화하는 문제입니다. 이동 방향은 아래로 떨어지며 펜스 끝점에서 좌우로 이동할 수 있습니다.
문제를 역방향으로 전환하여 위에서 아래로 낙하하는 과정으로 모델링합니다. `min_dist[i][0/1]`를 `i`번째 펜스의 좌/우 끝점에 도달하는 최소 수평 거리로 정의합니다. 이전 펜스를 추적하기 위해 x좌표별 마지막 덮개 구간을 관리하는 세그먼트 트리를 활용합니다. 구간 업데이트와 단일 포인트 쿼리를 통해 직전 펜스 인덱스를 빠르게 탐색하고, 절대 거리 차이를 더해 DP를 진행합니다.
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN = 30005;
const int OFFSET = 100000;
const int COORD_RANGE = 200005;
int tree_cover[COORD_RANGE * 4];
int min_horiz[MAXN][2];
int pen_L[MAXN], pen_R[MAXN];
int n, start_x;
void push_down(int node) {
if (tree_cover[node] != -1) {
tree_cover[2*node] = tree_cover[node];
tree_cover[2*node+1] = tree_cover[node];
tree_cover[node] = -1;
}
}
void update(int node, int start, int end, int l, int r, int val) {
if (r < start || end < l) return;
if (l <= start && end <= r) { tree_cover[node] = val; return; }
push_down(node);
int mid = (start + end) / 2;
update(2*node, start, mid, l, r, val);
update(2*node+1, mid+1, end, l, r, val);
}
int query(int node, int start, int end, int idx) {
if (start == end) return tree_cover[node];
push_down(node);
int mid = (start + end) / 2;
if (idx <= mid) return query(2*node, start, mid, idx);
return query(2*node+1, mid+1, end, idx);
}
int main() {
scanf("%d%d", &n, &start_x);
fill(tree_cover, tree_cover + COORD_RANGE * 4, -1);
pen_L[0] = pen_R[0] = OFFSET;
min_horiz[0][0] = min_horiz[0][1] = 0;
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &pen_L[i], &pen_R[i]);
int cl = pen_L[i] + OFFSET, cr = pen_R[i] + OFFSET;
int prev_idx_l = query(1, 0, 2*OFFSET, cl);
min_horiz[i][0] = min(min_horiz[prev_idx_l][0] + abs(pen_L[i] - pen_L[prev_idx_l]),
min_horiz[prev_idx_l][1] + abs(pen_L[i] - pen_R[prev_idx_l]));
int prev_idx_r = query(1, 0, 2*OFFSET, cr);
min_horiz[i][1] = min(min_horiz[prev_idx_r][0] + abs(pen_R[i] - pen_L[prev_idx_r]),
min_horiz[prev_idx_r][1] + abs(pen_R[i] - pen_R[prev_idx_r]));
update(1, 0, 2*OFFSET, cl, cr, i);
}
int end_x = start_x + OFFSET;
int ans = min(min_horiz[n][0] + abs(pen_L[n] + OFFSET - end_x),
min_horiz[n][1] + abs(pen_R[n] + OFFSET - end_x));
printf("%d\n", ans);
return 0;
}K. 건초 타워 최대 높이 (단조 큐 DP)
폭이 각각 다른 건초를 하단 폭이 상위 폭 이상이어야 한다는 조건으로 쌓아 올릴 때, 최대한 많은 층을 구성하는 문제입니다. 순서는 고정되어 있으며 역순으로 배치 전략을 수립할 수 있습니다.
최소 바닥 폭을 유지하면 최대 층수를 달성할 수 있다는 최적 부분 구조 성질이 성립합니다. `dp[i]`를 앞의 `i`개 건초로 만들 수 있는 최대 층수, `width[i]`를 해당 층 구성 시 하단 폭 최소값으로 정의합니다. 상태 전이 시 `width[j] < prefix_sum[i] - prefix_sum[j]` 조건을 만족하는 가장 큰 `j`를 찾아야 합니다. 이 부등식을 `width[j] + prefix_sum[j] < prefix_sum[i]`로 변환하면, 좌변이 단조 증가하는 구조이므로 단조 큐를 활용해 선형 시간에 최적 후보를 선별할 수 있습니다.
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
int weight[MAXN], prefix[MAXN], max_layers[MAXN], min_width[MAXN];
int mono_q[MAXN];
int n;
int main() {
scanf("%d", &n);
for (int i = n; i >= 1; --i) scanf("%d", &weight[i]);
prefix[0] = 0;
max_layers[0] = 0;
min_width[0] = 0;
int head = 1, tail = 1;
mono_q[1] = 0;
int global_max = 0;
for (int i = 1; i <= n; ++i) {
prefix[i] = prefix[i-1] + weight[i];
while (head < tail && min_width[mono_q[head]] + prefix[mono_q[head]] <= prefix[i]) {
head++;
}
int prev = mono_q[head];
max_layers[i] = max_layers[prev] + 1;
min_width[i] = prefix[i] - prefix[prev];
global_max = max(global_max, max_layers[i]);
while (head <= tail && min_width[mono_q[tail]] + prefix[mono_q[tail]] >= min_width[i] + prefix[i]) {
tail--;
}
mono_q[++tail] = i;
}
printf("%d\n", global_max);
return 0;
}