SWEA 2001. 파리 퇴치

• 문제 링크 : 2001. 파리 퇴치

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

문제 설명

N x N 배열 안의 숫자는 해당 영역에 존재하는 파리의 개수를 의미한다.
아래는 N=5 의 예이다.

M x M 크기의 파리채를 한 번 내리쳐 최대한 많은 파리를 죽이고자 한다.
죽은 파리의 개수를 구하라!
예를 들어 M=2 일 경우 위 예제의 정답은 49마리가 된다.

[제약 사항]

1. N 은 5 이상 15 이하이다.
2. M은 2 이상 N 이하이다.
3. 각 영역의 파리 갯수는 30 이하 이다.

[입력]

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에 N 과 M 이 주어지고,
다음 N 줄에 걸쳐 N x N 배열이 주어진다.

[출력]

출력의 각 줄은 '#t'로 시작하고, 공백을 한 칸 둔 다음 정답을 출력한다.
(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

입력
10
5 2
1 3 3 6 7
8 13 9 12 8
4 16 11 12 6
2 4 1 23 2
9 13 4 7 3
6 3
29 21 26 9 5 8
21 19 8 0 21 19
9 24 2 11 4 24
19 29 1 0 21 19
10 29 6 18 4 3
29 11 15 3 3 29
...

출력
#1 49
#2 159
...

1. 문제 해석

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

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

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;
}