전공공부
[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
'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 |