[백준] 단계별로 풀어보기(단계:16, 누적합,JAVA)11659번, 구간 합 구하기 4

문제 링크

11659번: 구간 합 구하기 4

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

누적합이란?

입력되는 값들의 누적합 값을 따로 저장하여 필요에 따라 사용하는 알고리즘입니다.

 

예를 들어 1 5 4 36 8이 입력되었을 때 누적합 값을 저장한 배열을 표로 표현하면

	1	5	4	36	8
누적합	1	6	10	46	54

 

이 문제에 핵심은

1. M개의 입력값에 따른 N개의 숫자 범위에서의 합을 결과로 출력해야 한다.

 

저는 이 문제를 누적합을 이용하여 간단하게 해결하였습니다.

 

사용한 배열

 

DP : 누적합 저장 배열

 

num : 입력되는 숫자 저장 배열

 

예제입력 1의 입력된 숫자들을 누적합에 대한 표로 나타내면

	5	4	3	2	1
누적합	5	9	12	14	15

 

i = 1, j = 3일 때는

1~3까지의 범위의 합을 구해야하기 때문에

5 + 4 + 3 = 12

 

i = 2, j = 4일 때는

2~4까지의 범위의 합을 구해야하기 때문에

4 + 3 + 2 = 9

 

여기서 규칙을 발견할 수 있습니다.

i = n, j = m일 때

n~m까지의 범위의 합 = DP[j] - DP[i-1]로 표현할 수 있습니다.

 

DP[0] = 0으로 초기화 했을 때

i = 1, j = 3일 때는

1~3의 범위의 합 = DP[3] - DP[0] = 12 - 0 = 12

 

i = 2, j = 4일 때는

2~4의 범위의 합 = DP[4] - DP[1] = 14 - 5 = 9

 

문제를 해결한 알고리즘의 과정입니다.

1. 입력값 N, M과 N개의 숫자와 M개의 범위를 받습니다.

2. N개의 숫자를 num에 저장할 때 누적합 DP도 같이 구합니다.

3. 범위와 규칙을 통해 해당 범위의 합을 구하여 결과로 출력합니다.

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해 N과 M, N개의 숫자, M개의 범위를 분리하였습니다.
• N개의 숫자를 저장할 때 DP도 같이 구하였습니다.
• BufferedWriter에 각 범위의 DP[i] - DP[i-1]의 값을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int N,M;
	static int[] num,DP;	//입력된 숫자 저장 배열, 누적합 저장 배열
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //------입력값 저장 및 배열 초기화---------
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	num = new int[N+1];
    	DP = new int[N+1];
    	st = new StringTokenizer(br.readLine()," ");
    	for(int i=1;i<=N;i++) {
    		num[i] = Integer.parseInt(st.nextToken());
    		DP[i] = DP[i-1] + num[i];		//누적합 DP값 저장
    	}

    	for(int s=0;s<M;s++) {
    		st = new StringTokenizer(br.readLine()," ");
    		int i = Integer.parseInt(st.nextToken());
    		int j = Integer.parseInt(st.nextToken());
    		bw.write(DP[j] - DP[i-1] + "\n");	//범위값 규칙 적용하여 BufferdWriter 저장
    	}
    	bw.flush();			//결과 출력
    	bw.close();
    	br.close();
    	
    }
    
}