[파이썬, 자바] 백준 2167 : 2차원 배열의 합 (실버5)

[파이썬, 자바] 백준 2167 : 2차원 배열의 합 (실버5)

• https://www.acmicpc.net/problem/2167

---

풀이

방향성 생각

• 입력이 작아서 for문으로 돌려도 되지만, 누적합을 사용해서 효율적으로 구하기.
• 누적합 배열을 만들 땐, 기존 배열보다 크기가 1씩 큰 배열을 만들어서 cumsum 배열과 인덱스가 일치하게 맞춰주자.

 

---

파이썬

import sys
input = lambda: sys.stdin.readline().rstrip()

H,W = map(int,input().split())

arr = [[0]*(W+1) for _ in range(H+1)]
for i in range(1,H+1):
    arr[i][1:] = list(map(int, input().split()))

# x,y 인덱스가 작은쪽에서 2번 더해지면 x-1,y-1쪽 데이터는 두 번 더해져서 빼기
cumsum = [[0]*(W+1) for _ in range(H+1)]
for i in range(1,H+1):
    for j in range(1,W+1):
        cumsum[i][j] = arr[i][j] + cumsum[i-1][j] + cumsum[i][j-1] - cumsum[i-1][j-1]

# 두 좌표가 주어지면 인덱스가 작은쪽에서 2번 빠지면, 겹치는 영역이 두 번 빼져서 더해주기
def get_sum(location):
    y1,x1,y2,x2 = location 
    return cumsum[y2][x2] - cumsum[y1-1][x2] - cumsum[y2][x1-1] + cumsum[y1-1][x1-1]

queries = [tuple(map(int,input().split())) for _ in range(int(input()))]
for query in queries:
    print(get_sum(query))

---

자바

import java.io.*;
import java.util.*;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int H = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());

        int[][] arr = new int[H+1][W+1];
        for (int i=1; i<H+1; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j=1; j<W+1; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[][] cumsum = new int[H+1][W+1];
        for (int i=1; i<H+1; i++) {
            for (int j=1; j<W+1; j++) {
                cumsum[i][j] = arr[i][j] + cumsum[i-1][j] + cumsum[i][j-1] - cumsum[i-1][j-1];
            }
        }        

        st = new StringTokenizer(br.readLine());
        int TC = Integer.parseInt(st.nextToken());

        for (int tc=0; tc<TC; tc++) {
            st = new StringTokenizer(br.readLine());
            int y1 = Integer.parseInt(st.nextToken());
            int x1 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            System.out.println(cumsum[y2][x2] - cumsum[y1-1][x2] - cumsum[y2][x1-1] + cumsum[y1-1][x1-1]);
        }
    }
}

---

코멘트

• .