[백준 2042번] 구간 합 구하기

난이도: 골드 I

문제 링크: https://www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

백준 2042번 문제 구간 합 구하기

이 문제는 세그먼트 트리라는 알고리즘을 알아야 풀 수 있는 문제입니다.

기본적인 설명은 여기를 참고해 주세요.

 

세그먼트 트리의 기본적인 문제입니다.

한 가지 유의할 점이 있다면, 값을 수정할 때입니다.

b의 값을 c만큼 수정하는 것이 아니라, b의 값을 c로 수정하는 것입니다.

따라서 차이값 difference  =  c - arr[b]가 되며, 차이값을 구할 때 arr을 참조하므로, arr[b]의 값 역시 수정하는 작업이 필요합니다.

이 외에는 세그먼트 트리 설명글과 거의 같으니 생략하겠습니다.

 

	#include <iostream>
	#include <vector>
	#include <cmath>
	using namespace std;
	int n, m, k;
	vector<long long> arr;
	int closest_square (vector<long long> &arr) {
	int a = (int)arr.size();
	int i = 1;
	while(1) {
	if (pow(i, 2) >= a) break;
	i++;
	}
	return pow(i,2) * 4;
	}
	long long segment_tree(vector<long long> &tree, int start, int end, int node) {
	if (start == end) return tree[node] = arr[start];
	int mid = (start + end) / 2;
	return tree[node] = segment_tree(tree, start, mid, node*2) + segment_tree(tree, mid+1, end, node*2+1);
	}
	long long get_sum (vector<long long> &tree, int start, int end, int left, int right, int node) {
	if (left > end || right < start) return 0;
	if (left <= start && end <= right) return tree[node];
	int mid = (start + end) / 2;
	return get_sum(tree, start, mid, left, right, node*2) + get_sum(tree, mid+1, end, left, right, node*2+1);
	}
	void edit_value(vector<long long> &tree, int start, int end, int node, int index, long long value) {
	if (index < start || index > end) return;
	tree[node] += value;
	if (start == end) return;
	int mid = (start + end) / 2;
	edit_value(tree, start, mid, node*2, index, value);
	edit_value(tree, mid+1, end, node*2+1, index, value);
	}
	int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m >> k;
	arr.push_back(-1);
	for (int i = 0; i < n; i++) {
	int temp;
	cin >> temp;
	arr.push_back(temp);
	}
	int square = closest_square(arr);
	vector<long long> tree(square);
	segment_tree(tree, 1, n, 1);
	for (int i = 0; i < m+k; i++) {
	int a, b;
	long long c;
	cin >> a >> b >> c;
	if (a == 1) {
	//값 변경
	long long difference = c - arr[b];
	arr[b] = c;
	edit_value(tree, 1, n, 1, b, difference);
	}
	else if (a == 2) {
	//구간 b, c의 합 출력
	cout << get_sum(tree, 1, n, b, c, 1) << '\n';
	}
	}
	return 0;
	}

view raw 2042_구간합구하기.cpp hosted with ❤ by GitHub

보통 이 문제는 채점 중 5% 지점에서 틀렸습니다 판정이 많이 나오는데,

앞서 말한 arr[b] 값 수정이 주된 원인이고, 또 하나는 tree의 크기를 너무 작게 잡으면 오답처리가 됩니다.

채점 결과

저도 위에서 언급한 두 부분에서 문제가 되어서 오답 판정을 여러 번 받았습니다 ㅠㅠ

세그먼트 트리의 가장 기초적인 문제라고 할 수 있는데 난이도가 골드 1이나 된다니... 실수할 여지가 많긴 하네요.