[알고리즘개념]구간합

11659. 구간 합 구하기 4

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	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 nm = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(nm.nextToken());
		int M = Integer.parseInt(nm.nextToken());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] arr = new int[N];
		int[] arr2 = new int[N];
		int sum = 0;
		for (int i = 0; i < N; i++) {
			int n = Integer.parseInt(st.nextToken());
			sum += n;
			arr[i] = n;
			arr2[i] = sum;
		}
		
		for (int i = 0; i < M; i++) {
			StringTokenizer st2 = new StringTokenizer(br.readLine());
			int l = Integer.parseInt(st2.nextToken()) - 1;
			int r = Integer.parseInt(st2.nextToken()) - 1;
			String res = String.valueOf(arr2[r] - arr2[l] + arr[l]);
			bw.write(res + "\n");
		}
		bw.close();
	}
}

구간 합 구하기 문제다. 배열에서 특정 구간의 요소들의 합을 구하는 건데, 배열 자체를 각 요소의 누적합으로 설정해주고 정해진 구간에 해당하는 인덱스의 값을 서로 빼주는 방식으로 풀면 된다. 난 이 과정에서 누락되는 요소를 처리해주기 위해서 배열을 두 개 사용하고 누락된 값을 추가로 더해주는 식으로 했는데, 이런 부분에서 최적화나 클린 코드에 대한 고민이 좀 더 필요하다. 다음 문제에서 이런 부분들을 보완해줬다.

 

11660. 구간 합 구하기 5

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	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[][] arr = new int[N + 1][N + 1];
		
		for (int i = 1; i < N + 1; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j < N + 1; j++) {
				arr[i][j] = arr[i - 1][j] + arr[i][j - 1] + Integer.parseInt(st.nextToken()) - arr[i - 1][j - 1];
			}
		}

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int x2 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());
			
			int res = arr[x2][y2] - arr[x1 - 1][y2] - arr[x2][y1 - 1] + arr[x1 - 1][y1 - 1];
			bw.write(String.valueOf(res) + "\n");
		}
		bw.close();
	}
}

2차원 배열을 이용한 구간 합 문제이다. 일단 누적합 배열을 만들 때 sum 변수를 따로 두지 않고 이전 인덱스의 값에 현재 토큰 값을 더해주는 식으로 개선했다. 이 때 방식은 x축, y축 기준으로 각각 이전 인덱스 값을 더해주고 겹치는 누적합을 빼준 다음 현재 토큰의 값을 더해준다. 2차원 배열의 크기를 주어진 길이보다 1씩 크게 만들어서 위쪽, 왼쪽에 빈 요소를 두는 것이 포인트다.

그리고 주어진 x1, y1, x2, y2 값에 대해

(x2, y2까지의 누적합) - (x1 - 1 행까지의 누적합) - (y1 - 1 열까지의 누적합) + (x1 - 1, y1 - 1까지의 누적합)

을 계산해서 결과로 출력한다.

알고보니 이전에 파이썬으로 실패했던 문제였다. 당시 구간합 개념을 몰라서 못풀었는데, 역시 개념이 탄탄해야 뭐든 풀 수 있는가보다. B형 치기 전에 열심히 공부해봐야겠다.