백준 16507번: 어두운 건 무서워 풀이

1. 백준 문제 기술

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

문제에서는 R×C 크기의 사진이 주어지고, 각 픽셀은 밝기 값을 가집니다. 그리고 Q개의 쿼리가 주어지는데, 각 쿼리는 두 점 (r1, c1)과 (r2, c2)를 꼭짓점으로 하는 직사각형 영역의 평균 밝기를 구하는 것입니다.

2. 문제의 핵심 요약

이 문제는 2차원 구간 합(2D Prefix Sum) 문제입니다. 각 쿼리마다 직사각형 영역의 합을 구하고 그 영역의 넓이로 나누어 평균을 구해야 합니다.

만약 각 쿼리마다 직접 해당 영역을 순회해서 합을 구한다면 시간복잡도가 O(Q × R × C)가 되어 시간 초과가 발생합니다. 따라서 전처리를 통해 2차원 누적합 배열을 만들어 O(1)에 구간 합을 구할 수 있도록 해야 합니다.

입력과 출력 형식의 이해

입력
- 사진 행과 열, 즉 크기(R×C)
- 밝기값들이 행렬(2차원 배열)로 주어짐
- 영역 쿼리 개수(Q)와, 각 쿼리별로 (r1, c1) ~ (r2, c2) 구간
출력
- 각 쿼리마다 해당 영역의 평균 밝기값을 소수 첫째 자리에서 반올림하여 출력

3. 해결하기 위한 아이디어 및 알고리즘 상세설명

2차원 누적합이란? 쉽게 풀어서 이해하기

2차원 누적합은 입력 행렬의 특정 직사각형 영역 합을 매우 빠르게 구하는 방법입니다.

핵심 아이디어: '미리' 누적합 배열을 만들어놓고, 네 꼭짓점의 값을 적절히 더하거나 빼서 원하는 영역의 합을 즉시 계산할 수 있습니다.

누적합 배열 S의 정의

S[i][j]는 첫 번째 행렬의 (1,1)부터 (i,j)까지의 모든 값의 합입니다.

S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + 사진[i][j]

원하는 영역의 밝기 합 빠르게 계산하기

아래의 공식만 외워두면, 어떤 직사각형 구간도 한 번에 계산할 수 있습니다!

구하고 싶은 영역: 왼쪽 위 (r1, c1), 오른쪽 아래 (r2, c2)

sum = S[r2][c2]
      - S[r1-1][c2]
      - S[r2][c1-1]
      + S[r1-1][c1-1]

이렇게 구한 뒤, 영역 내 칸 수로 나누면 평균값이 됩니다.

시간복잡도: O(R×C + Q) - 전처리 O(R×C), 각 쿼리 O(1)

4. 해답을 위한 단계별 설명

4.1. 입력 처리 및 배열 선언

#include <iostream>
using namespace std;

int main() {
    int R, C, Q;
    cin >> R >> C >> Q;
    
    // 1-indexed로 처리하기 위해 크기를 1씩 크게 잡음
    int arr[101][101];
    long long prefix[101][101] = {0};
    
    // 원본 배열 입력
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            cin >> arr[i][j];
        }
    }

4.2. 2차원 누적합 배열 구축

    // 2차원 누적합 배열 구축
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] 
                         - prefix[i-1][j-1] + arr[i][j];
        }
    }

4.3. 쿼리 처리

    // 쿼리 처리
    for (int q = 0; q < Q; q++) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        
        // 구간 합 계산
        long long sum = prefix[r2][c2] - prefix[r1-1][c2] 
                       - prefix[r2][c1-1] + prefix[r1-1][c1-1];
        
        // 영역의 넓이 계산
        long long area = (long long)(r2 - r1 + 1) * (c2 - c1 + 1);
        
        // 평균 계산 (정수 나눗셈)
        long long average = sum / area;
        
        cout << average << "n";
    }
    
    return 0;
}

5. 전체 코드

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int R, C, Q;
    cin >> R >> C >> Q;
    
    // 1-indexed로 처리하기 위해 크기를 1씩 크게 잡음
    int arr[101][101];
    long long prefix[101][101] = {0};
    
    // 원본 배열 입력
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            cin >> arr[i][j];
        }
    }
    
    // 2차원 누적합 배열 구축
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] 
                         - prefix[i-1][j-1] + arr[i][j];
        }
    }
    
    // 쿼리 처리
    for (int q = 0; q < Q; q++) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        
        // 구간 합 계산 (포함-배제 원리)
        long long sum = prefix[r2][c2] - prefix[r1-1][c2] 
                       - prefix[r2][c1-1] + prefix[r1-1][c1-1];
        
        // 영역의 넓이 계산
        long long area = (long long)(r2 - r1 + 1) * (c2 - c1 + 1);
        
        // 평균 계산 (정수 나눗셈)
        long long average = sum / area;
        
        cout << average << "n";
    }
    
    return 0;
}

코드 설명 및 주의사항

1-indexed 처리: 문제에서 좌표가 1부터 시작하므로 배열을 1-indexed로 처리합니다.
long long 사용: 누적합이 매우 클 수 있으므로 long long을 사용합니다.
경계 처리: prefix[0][j]와 prefix[i][0]은 모두 0으로 초기화되어 있어 경계 처리가 자연스럽게 됩니다.
정수 나눗셈: 문제에서 평균을 정수로 출력하라고 했으므로 정수 나눗셈을 사용합니다.
입출력 최적화: ios_base::sync_with_stdio(false)와 cin.tie(NULL)을 사용하여 입출력 속도를 향상시킵니다.

실전 팁 및 응용 예시

이 문제를 풀면, 모든 2차원 구간 합 문제에 자신감이 붙습니다!
예를 들어:
- 특정 영역의 누적합
- 이미지 처리
- 직사각형 카운팅
- 다양한 데이터 분석 문제 등

2차원 누적합 알고리즘은 한 번 익혀두면, 다양한 분야에 강력하게 활용할 수 있습니다.

한눈에 보는 핵심 요약

단계	설명
입력	M, N, Q 및 행렬 밝기값, 쿼리 구간
누적합 배열	S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + 사진[i][j]
영역합 공식	S[r2][c2] - S[r1-1][c2] - S[r2][c1-1] + S[r1-1][c1-1]
평균 밝기	영역합 / 영역 내 개수 → 소수 첫째 자리에서 반올림

이 구조와 공식을 암기해두면, 응용력과 문제해결 속도가 크게 향상됩니다.

결론 및 실전 활용법

2차원 누적합 알고리즘은 구간 합, 평균, 카운팅 등 다양한 곳에서 반복적으로 쓰입니다. 이 원리와 코드를 정확히 익혀두면, 실전 코딩 테스트에서 시간과 실수를 크게 줄일 수 있습니다.

연습: 직접 작은 예시 배열을 만들어 쿼리를 수행해보고, 공식의 동작을 스스로 확인해보세요!

백준 16507번 문제 풀이와 부분합 알고리즘 정리