[Python] 백준/BOJ 16507번: 어두운 건 무서워 (Silver 1)

💻 Problem

문제 보러 가기

 

호근이는 겁이 많아 어두운 것을 싫어한다. 호근이에게 어떤 사진을 보여주려는데 사진의 밝기가 평균 이상이 되지 않으면 일절 보려 하지 않는다. 호근이가 이 사진에서 일부분이라도 볼 수 있는 부분을 찾아주자.

 

 

위 그림은 호근이에게 보여줄 5×6 크기의 사진이며, 각 픽셀은 밝기를 나타낸다. 호근이가 사진의 일부분이라도 볼 수 있는지 알아보기 위해서는 두 점 (r1, c1)과 (r2, c2)를 꼭짓점으로 하는 직사각형의 밝기 평균을 구해야 한다. 예를 들어, 위 그림에서는 (2, 2)와 (4, 5)를 꼭짓점으로 하는 직사각형을 말한다.

호근이에게 보여줄 R×C 크기의 사진이 주어질 때, 사진의 일부분에 해당하는 밝기 평균을 구하여라.

 

💡 Approach

이 문제를 브루트포스로 풀게 될 경우, 최악의 경우 각각의 질의마다 그림의 전체 영역을 탐색 가능하므로 시간 복잡도는 O(Q * R * C)가 된다.

시간복잡도를 계산해보면 Q의 최댓값은 10^4, R과 C의 최댓값은 10^3이므로 1초(약 1억=10^8)를 초과하게 된다.

 

누적합으로 풀면 연산만으로 특정 영역의 합을 구할 수 있다.

1차원 배열 누적합은 기억나는데 2차원 배열 누적합은 오랜만에 보니 헷갈려서 이 글을 보니 이해가 잘 됐다.

 

예제 입력 1을 예시로 들자면, (2, 2)와 (4, 5)를 꼭짓점으로 하는 직사각형의 밝기 합을 구하기 위해서는

먼저 (0, 0)에서 (4, 5)의 사각형까지의 합을 구하고 (2, 2)에서 (4, 5)의 사각형을 벗어나는 영역(노란색, 연두색)을 제외해 준다.

노란색과 연두색 영역이 겹치는 부분은 2번 제외됐으므로 파란색 영역을 다시 더해야 한다.

 

즉, 빨간색 영역 - 주황색 영역 - 연두색 영역 + 파란색 영역을 구하면 된다.

 

이미 누적합이 적용된 2차원 배열이라고 생각하면

빨간색 칸의 값 - 주황색 칸의 값 - 연두색 칸의 값 + 파란색 칸의 값을 계산하여 구하면 된다.

 

✏️ Solution

R, C, Q = map(int, input().split())
picture = [[0] * (C + 1) for _ in range(R + 1)]

for i in range(1, R + 1):
    line = list(map(int, input().split()))
    for j in range(1, C + 1):
        picture[i][j] = line[j - 1] + picture[i][j - 1] + picture[i - 1][j] - picture[i - 1][j - 1]
        

for _ in range(Q):
    r1, c1, r2, c2 = map(int, input().split())
    print((picture[r2][c2] - picture[r1 - 1][c2] - picture[r2][c1 - 1] + picture[r1 - 1][c1 - 1]) // ((r2 - r1 + 1) * (c2 - c1 + 1)))

시간 복잡도는 입력 부분에서 R * C, 쿼리 부분에서 Q가 되므로 2,000 + 10,000 = 12,000이다.

• R, C = 1,000
• Q = 10,000