[백준] 16507 어두운 건 무서워 python

https://www.acmicpc.net/problem/16507

16507번: 어두운 건 무서워

이차원 배열을 사용한 누적합 문제이다

밝기의 평균을 구할때마다 항상 더하고 나누는 연산을 하는건 꽤 오래 걸린다. 그래서 누적합을 구한다음 특정 범위에서의 합을 구하고 해당 범위의 넓이로 나누면 된다.

일차원 배열에선 누적합을 구할땐 이전 인덱스 값만 계속 더해주면 되는데, 이차원 배열에서 누적합을 구할 땐 행과 열에서 이전 인덱스(memo[i-1][j], memo[i][j-1])를 더하고 중복으로 더해진 값인 대각선 값(memo[i-1][j-1])을 빼줘야한다. 그리고 원래 자리 값을 더하면 누적합 배열을 만들수 있다.

이렇게 구한 누적합 배열은 (1,1) 에서 (i,j) 까지의 누적합이다. 특정범위 (r1,c1), (r2,c2)의 누적 값을 구할때에도 비슷하게 접근하면 된다. 범위에서 필요없는 부분을 제거하고 중복 제거된 값을 다시 더해주면 된다.

area = memo[r2][c2] - memo[r1 - 1][c2] - memo[r2][c1 - 1] + memo[r1 - 1][c1 - 1]

특정 범위의 누적합을 구하고 특정 범위의 크기로 나누어주면 문제는 해결된다.

 

import sys; input = sys.stdin.readline

def main():
    R, C, Q = map(int, input().split())
    p = [list(map(int, input().split())) for _ in range(R)]
    memo = [[0 for _ in range(C + 1)] for _ in range(R + 1)]
    for i in range(1, R + 1):
        for j in range(1, C + 1):
            memo[i][j] = memo[i - 1][j] + memo[i][j - 1] - memo[i - 1][j - 1] + p[i - 1][j - 1]

    ans = []
    for _ in range(Q):
        r1, c1, r2, c2 = map(int, input().split())
        area = memo[r2][c2] - memo[r1 - 1][c2] - memo[r2][c1 - 1] + memo[r1 - 1][c1 - 1]
        num_of_area = (r2 - r1 + 1) * (c2 - c1 + 1)
        ans.append(area // num_of_area)
    print('\n'.join(map(str, ans)))


if __name__ == "__main__":
    main()

 

---

https://www.acmicpc.net/source/33805631

로그인

여기 풀이에서 itertools.accumulate를 사용해서 속도를 줄인 것을 확인할 수 있었다. for로 직접 구현하는 것보다 내장함수를 사용하는게 훨씬 빠르긴 하다고 들었는데 코딩테스트에서 사용할수 있을진 모르겠다. 

import sys; input = sys.stdin.readline
from itertools import accumulate

def main():
    R, C, Q = map(int, input().split())
    memo = [[0 for _ in range(C + 1)]]
    for i in range(1, R + 1):
        lst = [0]
        lst.extend(map(int, input().split()))
        memo.append(list(accumulate(lst)))

    for i in range(1, R + 1):
        for j in range(1, C + 1):
            memo[i][j] += memo[i - 1][j]

    ans = []
    for _ in range(Q):
        r1, c1, r2, c2 = map(int, input().split())
        area = memo[r2][c2] - memo[r1 - 1][c2] - memo[r2][c1 - 1] + memo[r1 - 1][c1 - 1]
        num_of_area = (r2 - r1 + 1) * (c2 - c1 + 1)
        ans.append(area // num_of_area)
    print('\n'.join(map(str, ans)))
    
if __name__ == "__main__":
    main()