[백준]구간 합 구하기4 JAVA

문제 링크

구간 합 구하기 문제는 실버부터 플레까지 난이도 폭이 크다. n값과 연산 처리 여부에 따라 난이도가 달라지는데, 4번은 실버 3으로 쉬운 편이다.

구간 합 문제 유형

이 유형으로는 아래와 같은데,

• 구간 합(a부터 b까지)
• 누적 합(0~c까지)
  풀이 알고리즘이 다양하다. 그래서 재밌당 ㅎㅎ
  구간 합 문제는

1. dp
2. 세그먼트 트리
3. 팬윅 트리
   와 같은 알고리즘을 통해 해결할 수 있다.

각각의 대한 설명은 다른 좋은 글이 있으니 링크만 남겨두겠다.
세그먼트 트리 설명 블로그
펜윅트리 설명 블로그

문제 풀이 빌드업

나는 펜윅트리와 dp를 사용해서 각각 풀어보았다.
펜윅트리는 누적합에 효율적이라 사실 세그먼트트리가 더 좋은 해결법이었겠지만, 난 펜윅이 좋다(구현하기 편하자너😛😌)

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를 할때 트리를 순회하게 되서 그런게 아닌가 싶다.
이유를 아시는 분은 댓글 부탁드립니다용