[SWEA] 2001. 파리 퇴치 c++

• 문제

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

M x M 크기의 파리채를 한 번 내리쳐 최대한 많은 파리를 죽이고자 한다.

파리를 잡을 수 있는 최댓값을 구하는 문제이다.

 

[제약 사항]

1. N 은 5 이상 15 이하이다.

2. M은 2 이상 N 이하이다.

3. 각 영역의 파리 갯수는 30 이하 이다.


[입력]

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에 N 과 M 이 주어지고,

다음 N 줄에 걸쳐 N x N 배열이 주어진다.


[출력]

출력의 각 줄은 '#t'로 시작하고, 공백을 한 칸 둔 다음 정답을 출력한다.

(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

 

 

input	output
2 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

• 문제 해결

나는 std::accumulate 함수를 사용하여 문제를 풀었다.

accumulate 함수는 vector 원소들의 합을 구하는 함수이다.

1. nxn 행, 열의 검사 index 범위는 ( 0~ n-m ) 번 이다.

2. mxm 값을 구하는 식을 세운다.

    1) 열 : i번 부터 i+m번의 합을 구한다. 

    2) 행 : j번 부터 j+m번 까지의 열들의 합을 구한다.

3. 최댓값 검사를 한다.

#include<iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

int main(int argc, char** argv)
{
	int test_case;
	int T;
	cin>>T;
	
	for(test_case = 1; test_case <= T; ++test_case)
	{
		int n = 0, m = 0;
        cin >> n >> m;
        
        vector<vector<int>> board(n, vector<int> (n, 0));
        for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
            	cin >> board[i][j];
            }
        }
        
        int nMax = INT8_MIN;
        for(int i = 0; i <= n - m; i++){
            for(int j = 0; j <= n - m; j++){
                int sum  = 0;
                for(int k = 0; k < m; k++){
                  	sum += accumulate(board[j+k].begin() + i, board[j+k].begin() +i+ m , 0);
                }
                nMax = max(nMax , sum);
            }      
        }
        cout << "#" << test_case << " ";
        cout << nMax << endl;
	}
	return 0;
}