7036 : 십자 합 최대
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 9
•통과: 1
•만든사람: suakii
문제 설명
$N \times N$ 크기의 정수 행렬이 주어집니다. 행렬 내의 한 지점 $(r, c)$를 기준으로 하여, 그 지점이 포함된 $r$행 전체의 합과 $c$열 전체의 합을 더한 것을 십자 합이라고 정의합니다.
단, 기준 지점의 원소 $A[r][c]$는 행 전체의 합과 열 전체의 합에 중복으로 포함되므로 한 번만 더해야 합니다.
행렬의 모든 가능한 지점 $(r, c)$ ($0 \le r, c < N$) 중에서 십자 합의 최댓값을 출력하는 프로그램을 작성하십시오.
[제약 조건]
• 행렬 크기 $N$: $3 \le N \le 1\,000$
• 각 원소의 절댓값: $\le 100$
단, 기준 지점의 원소 $A[r][c]$는 행 전체의 합과 열 전체의 합에 중복으로 포함되므로 한 번만 더해야 합니다.
행렬의 모든 가능한 지점 $(r, c)$ ($0 \le r, c < N$) 중에서 십자 합의 최댓값을 출력하는 프로그램을 작성하십시오.
[제약 조건]
• 행렬 크기 $N$: $3 \le N \le 1\,000$
• 각 원소의 절댓값: $\le 100$
입력 설명
첫째 줄에 행렬의 크기 $N$이 주어집니다. ($3 \le N \le 1\,000$)
둘째 줄부터 $N$개의 줄에 걸쳐 각 줄에 $N$개의 정수가 공백으로 구분되어 행렬의 원소로 주어집니다. 각 정수의 절댓값은 $100$ 이하입니다.
둘째 줄부터 $N$개의 줄에 걸쳐 각 줄에 $N$개의 정수가 공백으로 구분되어 행렬의 원소로 주어집니다. 각 정수의 절댓값은 $100$ 이하입니다.
출력 설명
행렬의 모든 지점 중에서 얻을 수 있는 십자 합의 최댓값을 정수형태로 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3
1 2 3
4 5 6
7 8 9
출력 예시
COPY
복사되었습니다!
복사되었습니다!
33도움
매 위치마다 행과 열의 합을 매번 새로 구하면 $O(N^3)$의 연산이 필요해 비효율적입니다. 각 행의 총합
row_sum[r]과 각 열의 총합 col_sum[c]을 미리 구한 뒤, $O(N^2)$ 루프로 row_sum[r] + col_sum[c] - A[r][c]를 갱신하며 최댓값을 찾습니다.