Notice
Recent Posts
Recent Comments
Link
«   2025/05   »
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31
Archives
Today
Total
관리 메뉴

전공공부

[BOJ_17123] 배열 놀이 본문

Study/Problem Solving

[BOJ_17123] 배열 놀이

monitor 2024. 5. 6. 17:02

설명


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

 행 누적합 배열 열 누적합 배열을 각각 두고 각 행 또는 열의 크기 만큼 각 배열에 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

 

'Study > Problem Solving' 카테고리의 다른 글

[BOJ_2630] 색종이 만들기  (0) 2024.05.27
[BOJ_1749] 점수따먹기  (0) 2024.05.12
[BOJ_21318] 피아노 체조  (0) 2024.04.29
[BOJ_20438] 출석 체크  (0) 2024.04.28
[BOJ_11000] 강의실 배정  (0) 2024.04.07