SWEA 2001. 파리 퇴치

게시 2020/04/22 수정 2026/10/07 작성자 August

조회 7 분 읽는 시간

문제 링크 : 2001. 파리 퇴치

문제 요약

N×N 격자의 각 칸에 파리 수가 적혀 있다. M×M 크기의 파리채를 격자 안 어딘가에 한 번 내리칠 때, 파리채가 덮는 칸들의 파리 수 합의 최댓값을 구한다. N은 5 이상 15 이하, M은 2 이상 N 이하, 각 칸의 파리 수는 30 이하이다. 각 테스트 케이스는 N, M과 격자로 주어지고, 출력은 #번호 최댓값 형식이다.

1. 문제 해석

이 문제는 삼성 SW 역량테스트의 전형적인 이차원 배열 완전탐색 문제의 기본형이다. 이때는 하나도 빠짐없이 탐색하는 것이 중요하다. 처음에 많이 실수하는 부분은 개인적으로는 인덱스와 범위와 관련한 실수이다. 그래도 이러한 유형의 문제에서 인덱스와 범위를 하나씩 꼼꼼히 확인하다보면 그러한 실수는 줄일 수 있었다.

우선, NxN배열의 0번째 칸 부터 MxM의 파리채를 마스킹 해가면서 이동한다. 마스킹 할 때마다 그 범위의 합을 구한다. 그리고 최댓값으로 계속 갱신한다. 로직은 매우 간단하다. 주의할 점은 (i,j)에서 마스킹을 하려고 한다면 i+m <= n && j+m <= n 인 범위 내에서만 탐색하면, 범위를 벗어나지 않고 완전탐색을 할 수 있다.

이 조건이 맞는 이유는 파리채가 차지하는 칸을 생각하면 알 수 있다. 왼쪽 위 모서리가 (i, j)인 M×M 파리채는 행 i부터 i+M-1까지, 열 j부터 j+M-1까지를 덮는다. 마지막 행 번호 i+M-1이 N-1 이하여야 배열 안에 있으므로 i+M ≤ N이 되고, 열도 같다. 즉 파리채를 놓을 수 있는 왼쪽 위 모서리는 (N-M+1)×(N-M+1)개다.

2. 문제 풀이

  
#include <iostream>
using namespace std;

int map[15][15];

int flapper(int x, int y, int m){ // 파리채를 마스킹해서 그 영역의 합을 구한다.
    int sum = 0;
    for(int i=x; i<x+m; ++i){
        for(int j=y; j<y+m; ++j){
            sum += map[i][j];
        }
    }
    return sum;
}

int solve(int n, int m){
    int answer = 0;
    for(int i=0; i<n; ++i){
        for(int j=0; j<n; ++j){
            if(i+m <= n && j+m <= n){ // 각 위치에서 파리채를 마스킹 해본다.
                answer = max(answer, flapper(i, j, m)); // 계속 최댓값으로 갱신
            }
        }
    }
    return answer;
}

int main(int argc, char** argv) {
    int test_case, T;
    //freopen("2001_input.txt", "r", stdin);
    cin >> T;
    for(test_case = 1; test_case <= T; ++test_case) {
        int N, M;
        cin >> N >> M;
        for(int i=0; i<N; ++i){
            for(int j=0; j<N; ++j) cin >> map[i][j];
        }
        cout << "#" << test_case << " " << solve(N, M) << endl;
    }
    return 0;
}

코드 읽기

flapper(x, y, m)은 왼쪽 위가 (x, y)인 M×M 영역의 합을 이중 반복문으로 직접 더한다.
solve(n, m)은 모든 칸을 왼쪽 위 후보로 보되, i+m <= n && j+m <= n을 만족할 때만 flapper를 부르고 최댓값을 갱신한다. 반복 범위를 처음부터 i <= n-m, j <= n-m으로 줄여도 결과는 같다.
파리 수가 모두 0 이상이므로 answer를 0으로 시작해도 최댓값을 놓치지 않는다.

복잡도

왼쪽 위 후보가 (N-M+1)²개이고, 후보마다 M²칸을 더하므로 O((N-M+1)² × M²)이다. N이 최대 15이므로 어떤 M이든 한 테스트 케이스에 수천 번 정도의 덧셈으로 끝난다. 제약이 작아서 완전탐색이 그대로 통하는 문제다.

2차원 누적 합으로 줄이기

N이 훨씬 커진다면 같은 칸을 여러 파리채가 반복해서 더하는 낭비가 커진다. 이럴 때는 2차원 누적 합을 쓴다. S[i][j]를 (0, 0)부터 (i-1, j-1)까지 직사각형의 합으로 미리 계산해 두면, 임의의 M×M 영역의 합을 덧셈과 뺄셈 네 번으로 구할 수 있다. 전체 시간은 O(N²)이 된다. 아래는 같은 입출력 형식으로 작성한 참고 풀이다.

  
#include <iostream>
#include <algorithm>
using namespace std;

int S[16][16]; // S[i][j]: (0,0)부터 (i-1,j-1)까지의 합

int main() {
    int T; cin >> T;
    for (int tc = 1; tc <= T; ++tc) {
        int N, M; cin >> N >> M;
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j) {
                int x; cin >> x;
                S[i][j] = x + S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1];
            }
        }
        int answer = 0;
        for (int i = M; i <= N; ++i) {
            for (int j = M; j <= N; ++j) {
                int sum = S[i][j] - S[i - M][j] - S[i][j - M] + S[i - M][j - M];
                answer = max(answer, sum);
            }
        }
        cout << "#" << tc << " " << answer << "\n";
    }
    return 0;
}

S[i][j] = x + S[i-1][j] + S[i][j-1] - S[i-1][j-1]에서 마지막 항을 빼는 이유는, 위쪽 직사각형과 왼쪽 직사각형이 겹치는 부분이 두 번 더해졌기 때문이다. 영역 합을 구할 때도 같은 원리로, 위쪽과 왼쪽을 빼면서 두 번 빠진 왼쪽 위 모서리 부분을 다시 더한다. 인덱스를 1부터 쓰면 i-1이나 i-M이 0이 되어도 배열 밖을 읽지 않으므로 경계 처리가 단순해진다.

ProblemSolving, SWEA