구간 합 구하기 문제는 실버부터 플레까지 난이도 폭이 크다. n값과 연산 처리 여부에 따라 난이도가 달라지는데, 4번은 실버 3으로 쉬운 편이다.
이 유형으로는 아래와 같은데,
각각의 대한 설명은 다른 좋은 글이 있으니 링크만 남겨두겠다.
세그먼트 트리 설명 블로그
펜윅트리 설명 블로그
나는 펜윅트리와 dp를 사용해서 각각 풀어보았다.
펜윅트리는 누적합에 효율적이라 사실 세그먼트트리가 더 좋은 해결법이었겠지만, 난 펜윅이 좋다(구현하기 편하자너😛😌)
public class 구간합구하기4Dp {
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st=new StringTokenizer(br.readLine());
int n=Integer.parseInt(st.nextToken());
int m=Integer.parseInt(st.nextToken());
//누적 합을 저장할 배열
int sum[]=new int[n+1];
st=new StringTokenizer(br.readLine());
for (int i = 1; i <= n; i++) {
int num=Integer.parseInt(st.nextToken());
//입력받으면서 누적합 계산
sum[i]=sum[i-1]+num;
}
for (int i = 0; i < m; i++) {
st=new StringTokenizer(br.readLine());
int start=Integer.parseInt(st.nextToken());
int end=Integer.parseInt(st.nextToken());
//sum[end]-sum[start]를 하면 start 원소가 빼지게 된다.
bw.write(Integer.toString(sum[end]-sum[start-1])+"\n");
}
bw.flush();
}
}
public class 구간합구하기4FenwickTree {
static int n;
static long[]fenwik;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
int m=sc.nextInt();
fenwik=new long[n+1];
//팬윅은 1부터 시작
for (int i = 1; i <=n; i++) {
int temp=sc.nextInt();
updateTree(i, temp);
}
for (int i = 0; i < m; i++) {
int a=sc.nextInt();
int b=sc.nextInt();
long answer=sum(b)-sum(a-1);
System.out.println(answer);
}
}
//트리 초기화/갱신 메소드.
static void updateTree(int index,int val) {
while(index<=n) {
fenwik[index]+=val;
index+=index&-index;
}
}
//누적합 계산 메소드
static long sum(int index) {
long result=0;
while(index>0) {
result+=fenwik[index];
index-=index&-index;
}
return result;
}
}
두 방법으로 풀고 메모리와 시간을 보니 차이가 많이 났다.
위에가 dp고 오래 걸린 아래가 펜윅트리이다.
짧은 알고리즘 실력으로는 펜윅트리는 누적합 계산을 위한 update를 할때 트리를 순회하게 되서 그런게 아닌가 싶다.
이유를 아시는 분은 댓글 부탁드립니다용