https://www.acmicpc.net/problem/15678
[필자 사고]
이 문제는 세그먼트트리와 동적 프로그래밍을 합한 문제이다.
기존 세그먼트트리는 단순히 어떤 구간 내에서 최댓값 최솟값 합 등등을 구하는 문제만 풀어왔는데
동적프로그래밍을 합할 경우 현재 자신이조사하려는 idx기준으로 idx-1 이전의 구간의 최댓값을 계속 갱신해야 된다.
동적프로그래밍은 따로 날잡아서 계쏙 풀다보면 문제에 대한 접근이 생길것이다.
[코드 해설]
. 입력 데이터 처리 및 초기화 (Input 함수)
- N: 입력 데이터의 개수.
- D: 유효 구간의 범위.
- 세그먼트 트리 tree는 길이 4 * N + 1로 초기화되며, 모든 값을 LONG_MIN으로 설정합니다.
- LONG_MIN은 세그먼트 트리에서 구간 내 최대값을 찾는 과정에서 초기값으로 사용됩니다.
2. 구간 최대값 쿼리 (Query 함수)
- 구간 [left, right]에서 최대값을 구합니다.
- 현재 노드의 구간 [start, end]가 쿼리 범위에 완전히 포함되면, 해당 노드 값을 반환합니다.
- 구간이 겹치지 않으면 LONG_MIN을 반환합니다.
- 구간이 일부만 겹치는 경우, 왼쪽 자식 노드와 오른쪽 자식 노드에서 최대값을 각각 계산하고 그 중 최대값을 반환합니다.
3. 값 업데이트 (Update 함수)
- 배열의 특정 인덱스 idx를 val로 갱신합니다.
- 세그먼트 트리의 리프 노드에 값을 업데이트하고, 재귀적으로 부모 노드로 올라가면서 값을 갱신합니다.
- 부모 노드는 왼쪽 자식과 오른쪽 자식의 최대값을 저장합니다.
4. 메인 로직 (Game_Start 함수)
- N개의 숫자를 입력받아 처리합니다.
- 각 숫자 num에 대해:
- 현재 인덱스 i에서 유효 구간 [max(1, i-D), max(1, i-1)]의 최대값을 계산합니다.
- 유효 구간은 현재 숫자 num 앞의 최대 D개 숫자로 제한됩니다.
- 유효 구간의 최대값이 존재하지 않으면 기본값 0을 사용합니다.
- 위에서 계산한 최대값에 num을 더하여 새로운 maxValue를 구합니다.
- 해당 값을 세그먼트 트리에서 인덱스 i에 업데이트합니다.
- 현재 인덱스 i에서 유효 구간 [max(1, i-D), max(1, i-1)]의 최대값을 계산합니다.
- 모든 숫자 처리 후, 구간 [1, N]에서 최대값을 출력합니다.
[소스 코드]
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
int N, D;
vector <long > tree;
void Input() {
cin >> N >> D;
tree.resize(4 * N + 1,LONG_MIN);
}
long Query(int node, int start, int end, int left, int right) {
if (left <= start && end <= right) {
return tree[node];
}
if (end < left || right < start)return LONG_MIN;
int mid = (start + end) / 2;
return max(Query(node*2, start, mid, left, right),
Query(node*2+1, mid + 1, end, left, right));
}
void Update(int node, int start, int end, int idx, long val) {
if (idx < start || end < idx)return;
if (start == end) {
tree[node] = val;
return;
}
int mid = (start + end) / 2;
if (mid >= idx) {
Update(node * 2, start, mid, idx, val);
}
else {
Update(node * 2 + 1, mid + 1, end, idx, val);
}
tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
}
void Game_Start() {
for (int i = 1; i <= N; i++) {
long num;
cin >> num;
long maxValue=max(0L,Query(1, 1, N, max(1, i - D), max(1, i-1)))+num;
Update(1, 1, N, i, maxValue);
}
cout << Query(1, 1, N, 1, N);
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Input();
Game_Start();
}