[P5] 백준 27989번 가장 큰 증가하는 부분 수열 2 C++ 세그먼트 트리

리뷰

https://www.acmicpc.net/problem/27989

처음엔 Lis로 접근하였다가 엣지케이스가 존재하여 Fail을 받았다.

그 후로 세그먼트 트리를 통해 접근하였는데 분명 로직은 맞는데 계속 틀렸다.

알고보니 정수범위 초과로 인한 오버플로우로 매우 큰값을 넣었을 때의 엣지케이스를 발견했다.

그 뒤로 vector을 set으로 변환하는 과정에서 뭘 잘못건드렸는지 계속 또 틀림이 반복되었다.

결국 존재하는 int를 모두 long long타입으로 변환하여 set을 사용한 풀이도 AC를 받았다.

 

 

전역 변수

1. M : 주어지는 수열의 크기의 최대값을 저장하기 위한 상수타입 변수
2. n : 주어지는 수열의 크기를 저장할 변수
3. lst : 수열의 정보를 입력 받아 저장하기 위한 정수형 배열
4. tree : 최대값 세그먼트 트리를 저장하기 위한 정수형 배열
5. zip : 수열 내에서 중복을 제거한 값을 오름차순으로 정렬하기 위한 set
6. index : zip의 요소를 오름차순으로 인덱싱을 하기 위한 map

 

함수

1. query

ll query(int node, int s, int e, int L, int R)

 

구간 내 최대값을 찾아 출력하기 위한 함수

1. 매개변수로 세그먼트 트리의 노드 node, 탐색 범위 s, e 구간 범위 L, R을 전달받는다.
2. 만약 탐색 범위가 구간 범위를 벗어났을 경우 0을 리턴해 준다.
3. 구간 범위가 탐색 범위 안에 포함되는 경우 세그먼트 트리의 노드값을 리턴해 준다.
4. 현재 노드의 좌, 우 자식 노드로 재귀탐색을 시작하고, 두 노드 중 큰 값을 리턴한다.

 

2. update

void update(int node, int s, int e, int idx, ll val)

 

트리의 리프 노드를 업데이트 하고 상위 노드를 최대값으로 갱신하는 함수

1. 매개변수로 세그먼트 트리의 노드 node, 탐색 범위 s, e 업데이트할 인덱스 idx, 값 val를 전달받는다.
2. 리프 노드에 도달한 경우 해당 인덱스의 값을 val로 교체해 준다.
3. 리프노드가 아닐 경우 좌, 우 자식 노드로 재귀탐색을 시작한다.
4. 재귀를 빠져나오면서 세그먼트 트리의 노드를 자식 노드 중 더 큰값으로 업데이트 해준다.

 

문제풀이

1. n을 입력 받고, n개의 요소를 배열 lst에 입력 받아주고, zip에 해당 값을 insert해준다.
2. idx를 1로, len을 zip의 사이즈로 초기화 해준다.
3. zip을 순회하며 값 i를 index의 key로, idx를 value로 저장한 후 idx를 증가시켜준다.
4. 순회를 마친 후 정답을 저장할 변수 ans를 0으로 초기화 해준다.
5. 수열의 요소를 각각 순회하며 index에 해당 값을 전달하여 인덱스를 cur에 받아준다.
6. query함수를 호출하여 해당 인덱스 -1번째 까지의 최대값을 구한 뒤 max_val에 저장해 준다.
7. max_val에 현재 요소의 값을 더한 후 update함수를 호출하여 해당 인덱스의 값을 max_val로 변경한다.
8. ans에 max_val과 ans 중 더 큰값을 저장해 준다.
9. 모든 탐색을 마친 후 ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

1. 변수나 자료구조를 모두 long long타입으로 변경했으나 계속 Fail을 받았다.
2. 결국 찾아낸 문제점은 update함수의 매개변수 val또한 ll타입으로 바꿔주어야 했다.

 

참고 사항

• 수열의 요소에서 중복을 제거해 주어야 중복 연산을 피할 수 있다.
• 세그먼트 트리를 구성할 때 탐색 범위는 n이 아닌 중복 제거한 수열의 크기여야 한다.
• 해당 문제는 1-based-index를 사용해야 가독성이 좋은 것 같다.
• set을 사용하는 것 보다 vector사용 후 unique로 중복을 제거해 주는 것이 더 빠르다.

 

정답 코드

#include<iostream>
#include<set>
#include<map>
#define ll long long
using namespace std;

const int M = 300000;
int n;
ll lst[M];
ll tree[M * 4];
set<ll> zip;
map<ll, int> index;

void update(int node, int s, int e, int idx, ll val) {
	if (s == e) tree[node] = val;
	else {
		int mid = (s + e) / 2;
		if (idx <= mid) update(node * 2, s, mid, idx, val);
		else update(node * 2 + 1, mid + 1, e, idx, val);
		tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
	}
}

ll query(int node, int s, int e, int L, int R) {
	if (R < s || e < L) return 0;
	if (L <= s && e <= R) return tree[node];
	int mid = (s + e) / 2;
	return max(query(node * 2, s, mid, L, R), query(node * 2 + 1, mid + 1, e, L, R));
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> lst[i];
		zip.insert(lst[i]);
	}

	int idx = 1, len = zip.size();
	for (ll i : zip) index[i] = idx++;

	ll ans = 0;
	for (int i = 0; i < n; ++i) {
		int cur = index[lst[i]];
		ll max_val = query(1, 1, len, 1, cur - 1);
		max_val += lst[i];
		update(1, 1, len, cur, max_val);
		ans = max(ans, max_val);
	}
	cout << ans;
}