[백준, 파이썬, 17123번] 배열 놀이

 

풀이

• 처음 접근한 방법은
  • 문제처럼 2차원 배열의 값을 계속해서 변경한 다음
  • 반복문을 통해 가로, 세로의 합을 출력하는 형식으로 제출했으나... 시간초과
• 한참을 코드 수정하고 했지만 잘 안되서 서칭을 한 뒤 힌트를 얻게 되었는데
• 힌트는
  • 2차원 배열의 값을 바꾸는 것보다 합산한 값을 미리 만들어 둔 다음
  • 입력값으로 받아오는 v의 값을 누적합 하여 계산하는 방법.
• 그래서 미리 result에 배열을 만든 다음 가로, 세로 값을 0,1번째 인덱스에 추가
• 이후 v의 값을 위치에 맞게 누적합하여 출력해서 해결

 

정답 코드

import sys

input = sys.stdin.readline

for _ in range(int(input())):

    n,m = map(int,input().rstrip('\n').split())

    arr = [ list(map(int,input().rstrip('\n').split())) for _ in range(n)]

    result = [[],[]]

    for i in range(n): result[0].append(sum(arr[i]))

    for i in range(n): result[1].append(sum([arr[j][i] for j in range(n)]))

    for _ in range(m):

        r1, c1, r2, c2, v = map(int,input().rstrip('\n').split())

        for i in range(r1-1,r2): result[0][i] += (c2-c1+1)*v

        for i in range(c1-1,c2): result[1][i] += (r2-r1+1)*v

    [print(*i) for i in result]

 

처음 제출한 시간초과 코드

import sys

input = sys.stdin.readline

for _ in range(int(input())):

    n,m = map(int,input().rstrip('\n').split())

    arr = [ list(map(int,input().rstrip('\n').split())) for _ in range(n)]

    result = [[],[]]

    for _ in range(m):

        r1, c1, r2, c2, v = map(int,input().rstrip('\n').split())

        for i in range(r1-1,r2):

            for j in range(c1-1,c2):

                arr[i][j] += v

    [print(sum(arr[i]), end=' ') for i in range(n)]

    print()

    for i in range(n):

        hap = 0

        for j in range(n): hap += arr[j][i]

        print(hap, end=' ')

    print()