백준 16993, Segment Tree
Segment tree 의 특성을 활용하는 문제다.
특정 구간의 최대 합을 저장한다는 naive 한 접근에서 한 걸음 더 생각해야 한다.
각 노드 별로 아래와 같은 정보를 저장하면 된다.
Segtree 는 분할 정복의 memoization 이라는 말을 이 문제를 소개 받으며 들었는데,
그 점에서 segtree 는 분할정복 문제를 푸는 일종의 DP 기법이라고도 생각할 수 있다는 힌트를 얻었다.
[s,e] 구간 주어졌을때,
lmax: s 부터 시작하는 구간 중 최대 합
rmax: e 로 끝나는 구간 중 최대 합
mid_max: 가운데를 지나가는 구간의 최대 합
Source Code
//https://www.acmicpc.net/problem/16993
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define MAXI 1000000000
#define cplx complex<double>
const double PI = acos(-1);
const ll INF = LLONG_MAX / 4;
#define Msize 100100
struct tup{
/*
[s,e] 구간 주어졌을때,
lmax: s 부터 시작하는 구간 중 최대 합
rmax: e 로 끝나는 구간 중 최대 합
mid_max: 가운데를 지나가는 구간의 최대 합
*/
ll lmax, rmax, mid_max;
};
ll psum[Msize];
ll input[Msize];
struct segtree {
tup tree[4 * Msize];
segtree() {
memset(tree, 0, sizeof(tree));
}
tup init(int left, int right, int node) {
tree[node] = {-INF, -INF, -INF};
//init(1,N,1)
if (left == right) {
tree[node] = { input[left], input[left], input[left]};
return tree[node];
}
int mid = (left + right) / 2;
tup linit, rinit;
tup &ret = tree[node];
ll lpsum = 0, rpsum = 0;
linit = init(left, mid, node * 2);
rinit = init(mid + 1, right, node * 2 + 1);
//lmax: ([left, mid] 구간 lmax) OR ([left, mid] 구간 합 + [mid+1,right] 구간 lmax)
ret.lmax = max(linit.lmax, psum[mid] - psum[left - 1] + rinit.lmax);
//rmax: lmax vice versa
ret.rmax = max(rinit.rmax, psum[right] - psum[mid] + linit.rmax);
//mid_max: [left, mid] 구간 최댓값 OR [mid+1,right] 구간 최댓값 OR linit.rmax 과 rinit.lmax 이어 붙인것
ret.mid_max = max({linit.mid_max, rinit.mid_max, linit.rmax + rinit.lmax});
return tree[node];
}
tup query(int left, int right, int node, int nodeLeft, int nodeRight) {
//query(left,right,1,1,N);
tup ret = {-INF, -INF, -INF};
if (left > nodeRight || right < nodeLeft){
return ret;
}
if (left <= nodeLeft && right >= nodeRight){
return tree[node];
}
int mid = (nodeLeft + nodeRight) / 2;
tup lquery, rquery;
lquery = query(left, right, node * 2, nodeLeft, mid);
rquery = query(left, right, node * 2 + 1, mid + 1, nodeRight);
// init의 lmax, rmax, mid_max 와 동일.
// 단지 구간이 nodeLeft, mid, nodeRight 으로 바뀜.
ret.lmax = max(lquery.lmax, rquery.lmax + psum[mid] - psum[nodeLeft - 1]);
ret.rmax = max(rquery.rmax, lquery.rmax + psum[nodeRight] - psum[mid]);
ret.mid_max = max({lquery.mid_max, rquery.mid_max, lquery.rmax + rquery.lmax});
return ret;
}
};
int N, Q;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//ifstream cin; cin.open("input.txt");
psum[0] = 0;
input[0] = 0;
cin >> N;
for (int i = 1; i <= N;++i){
cin >> input[i];
psum[i] = psum[i - 1] + input[i];
}
segtree SEG;
SEG.init(1, N, 1);
cin >> Q;
while(Q--){
int s, e;
cin >> s >> e;
tup q = SEG.query(s, e, 1, 1, N);
//printf("%lld\n", max({q.lmax, q.rmax, q.mid_max})); // 왜 이건 안될까?
printf("%lld\n", q.mid_max);
}
return 0;
}
PREVIOUSPS/CP 책 리뷰 모음