【경쟁 프로 전형적인 90문】004의 해설(python)

개요

경쟁 프로 전형 90문 의 해설 기사입니다.
해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다.

※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다.
※★5이상의 문제는 난이도적으로 후회하고 있기 때문에, 투고 시기가 늦어질 가능성이 있습니다. (대신 정중하게 해설 해 주시는 분이라면 꼭 부탁드립니다)

이슈004-크로스섬

문제 개요

매스(i, j)와 같은 행, 같은 열에 있는 매스의 합계치를 모든 매스로 구한다.

제약

2 <= H, W <= 2000 \\
1 <= Ai <= 99 \\

・입력은 모두 정수.

해결 방법

우선 처음에, 모든 매스에 있어서, 차례로 합계치를 구해 가는 방법을 생각할 수 있을까 생각합니다.
이 생각에서는, 매스의 총수가 $HW≒10^6$로 각 매스에 있어서의 처리가 $H+W≒10^3$가 되기 때문에, TLE가 되어 버립니다.

위의 방법에서는 각 행, 각 열의 합계를 반복해 구해 버립니다.
그래서, 이번에는, 미리 각 행, 각 열의 합계를 구해 두고, 그 조합을 모든 매스에 대해, 구하는 수단을 취합니다. (이 방법에서는, A[i][j]가 이중으로 더해지므로, 1분 감산하는 점에 주의해 주세요.)

구현의 흐름은 다음과 같습니다.
1. 각 행 H, 열 W의 합을 각각 구한다.
2. 매스 i, j 와 같은 행, 같은 열에 있는 매스의 합계치를 구한다.

1의 처리에서도 2의 처리에서도 $HW$,
즉 $10^6$ 의 주문으로 요구되기 때문에, 충분히 사이에 맞습니다.



인용 소스 : 경쟁 프로 전형 90문 Github

구현

answer.py

# 入力の受け取り
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]

# 各行の和をLに格納する
L = []
for i in range(H):
  L.append(sum(B[i]))

# 各列の和をRに格納する
R = []
for i in range(W):
  cnt = 0
  for j in range(H):
    cnt += B[j][i]
  R.append(cnt)

# 各マスにおいての行と列の合計値を求め、二重に加算されているA[i][j]を減算する。
B = []

for i in range(H):
  l = []
  for j in range(W):
    sums = L[i] + R[j] - A[i][j]
    l.append(sums)
  B.append(l)

# 答えを出力する
for i in range(H):
  print(*B[i])

마지막으로

이번 문제는 필요한 값을 미리 계산하는 것이 큰 포인트였습니다.

문제의 해설을 읽어도 다른 사람의 코드를 봐도 확실히 모르는 분
힘에 조금이라도 될 수 있으면 다행입니다.
코드의 개선점이나 그 외, 의견등 있으면, 부담없이 코멘트해 주세요.
또, 이 기사를 읽고 이해할 수 있었던 분은 꼭 LGTM를 눌러 주실 수 있으면 기쁩니다.
(기사 투고의 모티베가 됩니다.)

여기까지 읽어 주셔서 감사합니다.