[BOJ_17123] 배열 놀이

설명

---

간단히 누적합을 떠올려서 풀 수 있었던 문제입니다. 일일이 문제 조건을 카운트한다면 시간 초과가 날 것이 뻔했기 때문에 우선 문제 조건 중 각 원소들의 행의 합과 각 원소들의 열의 합을 구한다는 것에 포커스를 맞춰 접근했습니다.

 행 누적합 배열 열 누적합 배열을 각각 두고 각 행 또는 열의 크기 만큼 각 배열에 V 값을 더해주되 열 배열일때는 행의 크기만큼 v를 곱해서 누적하고 반대로 행 배열일때는 열의 크기 만큼 v를 곱해서 누적하는 배열을 만들어 그대로 출력하였습니다.

 

코드

---

package BOJ.prefix_sum;

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

public class BOJ_17123 {
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");
        StringBuilder sb = new StringBuilder();
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(tk.nextToken());

        while (T-- > 0){
            tk = new StringTokenizer(in.readLine()," ");
            int N = Integer.parseInt(tk.nextToken());
            int M = Integer.parseInt(tk.nextToken());

            int[][] arr = new int[N][N];
            int[] A = new int[N];
            int[] B = new int[N];
            for (int i = 0; i < N; i++){
                tk = new StringTokenizer(in.readLine()," ");
                for (int j = 0; j < N; j++){
                    arr[i][j] = Integer.parseInt(tk.nextToken());
                    A[i] += arr[i][j];
                }
            }
            for (int j = 0; j < N; j++){
                for (int i = 0; i < N; i++){
                    B[j] += arr[i][j];
                }
            }
            for (int i = 0; i < M; i++){
                tk = new StringTokenizer(in.readLine()," ");
                int r1 = Integer.parseInt(tk.nextToken()) - 1;
                int c1 = Integer.parseInt(tk.nextToken()) - 1;
                int r2 = Integer.parseInt(tk.nextToken()) - 1;
                int c2 = Integer.parseInt(tk.nextToken()) - 1;
                int v = Integer.parseInt(tk.nextToken());

                for (int j = r1; j <= r2; j++){
                    A[j] += (v *((c2 + 1) - c1));
                }
                for (int j = c1; j <= c2; j++){
                    B[j] += (v*((r2 + 1) - r1));
                }
            }
            for (int i = 0; i < N; i++){
                sb.append(A[i] + " ");
            }
            sb.append("\n");
            for (int i = 0; i < N; i++){
                sb.append(B[i] + " ");
            }
            sb.append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

https://www.acmicpc.net/problem/17123