[백준/JAVA] 2042번: 구간 합 구하기
🔺 문제
2042번: 구간 합 구하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄
www.acmicpc.net
🔺 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
import java.util.*;
import java.io.*;
public class Main {
static long[] tree; // 세그먼트 트리 배열
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
int N = Integer.parseInt(st.nextToken()); // 데이터 개수
int M = Integer.parseInt(st.nextToken()); // 변경 횟수
int K = Integer.parseInt(st.nextToken()); // 구간 합 구한 횟수
// 트리 배열 채우기 (구간 합)
int treeHeight = 0;
int len = N;
while(len != 0) {
len /= 2;
treeHeight++;
}
int treeSize = (int)Math.pow(2, treeHeight + 1);
int leftNodeStartIdx = treeSize / 2 - 1; // 리프 노드 시작 idx
tree = new long[treeSize + 1];
for(int i = leftNodeStartIdx + 1 ; i <= leftNodeStartIdx + N ; i++) {
tree[i] = Long.parseLong(br.readLine());
}
setTree(treeSize - 1); // 트리 생성
for(int i = 0 ; i < (M + K) ; i++) {
st = new StringTokenizer(br.readLine()," ");
long a = Long.parseLong(st.nextToken()); // 질의 유형
int s = Integer.parseInt(st.nextToken()); // 시작 idx
long e = Long.parseLong(st.nextToken()); // 종료 idx / 변경값
// 업데이트
if(a == 1) {
changeVal(leftNodeStartIdx + s, e);
}
// 구간 합 계산
else if(a == 2){
s += leftNodeStartIdx;
e += leftNodeStartIdx;
System.out.println(getSum(s, (int) e));
}
else {
return;
}
}
br.close();
}
// 구간 합 계산 함수
private static long getSum(int s, int e) {
long partSum = 0;
while(s <= e) {
if(s % 2 == 1) {
partSum += tree[s];
s++;
}
if(e % 2 == 0) {
partSum += tree[e];
e--;
}
s /= 2;
e /= 2;
}
return partSum;
}
// 값 변경 함수
private static void changeVal(int idx, long val) {
long diff = val - tree[idx];
while(idx > 0) {
tree[idx] += diff;
idx /= 2;
}
}
// 초기 트리 구성 함수
private static void setTree(int i) {
while(i != 1) {
tree[i / 2] += tree[i]; // 각 노드 값을 부모 노드로 누적해 저장
i--;
}
}
}
|
cs |
✅ 해결 아이디어
✔ 세그먼트 트리
- 값 변경이 빈번하게 일어나므로 세그먼트 트리 이용
🔺 다른 풀이들
[BOJ] 백준 2042번 : 구간 합 구하기 (JAVA)
문제 어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번
steady-coding.tistory.com
[Java] 백준 2042번 구간 합 구하기
세그먼트 트리 문제입니다. 수열이 주어지고 중간에 수열안의 값들이 자주 변경됩니다. 이 때 주어진 구간의 합을 출력하여야 합니다. 구간의 합을 구하는데 걸리는 시간은 O(N)입니다. 100만 * 100
j3sung.tistory.com
[JAVA/백준] 2042번: 구간 합 구하기
PS & 개발 기록
iamheesoo.github.io
[JAVA] 세그먼트 트리 (Segment Tree)
Segment Tree 란? 데이터 집합이 주어지고, 특정 구간의 합, 최대, 최소 값을 구해야하는 문제가 주어짐 이 때, 구간이 여러개이거나 데이터가 업데이트 될 수 있는 상황에서 더 빠르게 찾아내기 위
chb2005.tistory.com
💬 느낀 점
연습을 합시닷...
| 1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
| V |
(참고)
✔ 세그먼트 트리
41. 세그먼트 트리(Segment Tree)
이번 시간에 다룰 내용은 여러 개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터의 합을 구하는 ...
blog.naver.com