4095 : 2D 십자 합
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 4
•통과: 2
•만든사람: suakii
문제 설명
$N \times M$ 크기의 격자 배열과 특정 위치 $(r, c)$를 나타내는 $Q$개의 쿼리가 주어질 때, 각 쿼리마다 $(r, c)$ 위치의 행 전체 원소의 합과 열 전체 원소의 합을 구하여 중복된 교차점 원소의 값을 $1$번만 뺀 '십자 합'을 구하는 프로그램을 작성하시오.
십자 합 = $r$행 전체 합 + $c$열 전체 합 - 격자$[r][c]$
[제약 조건]
• $1 \le N, M \le 100$
• $1 \le Q \le 100$
• $1 \le r \le N$, $1 \le c \le M$
• $-1000 \le (\text{격자 내 각 원소}) \le 1000$
• 입력되는 모든 값은 정수
[제약 조건]
• $1 \le N, M \le 100$
• $1 \le Q \le 100$
• $1 \le r \le N$, $1 \le c \le M$
• $-1000 \le (\text{격자 내 각 원소}) \le 1000$
• 입력되는 모든 값은 정수
입력 설명
첫째 줄에 행렬의 크기 $N$과 $M$이 공백으로 구분되어 주어집니다.
둘째 줄부터 $N$개의 줄에 걸쳐 각 행의 $M$개의 정수가 공백으로 구분되어 주어집니다.
그 다음 줄에 쿼리의 수 $Q$가 주어지고, 이후 $Q$개의 줄에 각각 쿼리 $r, c$가 공백으로 구분되어 주어집니다.
둘째 줄부터 $N$개의 줄에 걸쳐 각 행의 $M$개의 정수가 공백으로 구분되어 주어집니다.
그 다음 줄에 쿼리의 수 $Q$가 주어지고, 이후 $Q$개의 줄에 각각 쿼리 $r, c$가 공백으로 구분되어 주어집니다.
출력 설명
각 쿼리별 십자 합의 결과를 한 줄에 하나씩 순서대로 출력한다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3
35 75 7
-40 -65 5
-55 48 -12
1
2 2
출력 예시
COPY
복사되었습니다!
복사되었습니다!
23도움
행 합과 열 합을 미리 계산(Prefix Sum 혹은 pre-calculation)해 놓으면 시간 효율이 크게 향상된다.