SWEA 2001 | 파리 퇴치

Problem 💻

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
...

---

Approach 1 ❌

• 완전 탐색(브루트포스) 방식으로 접근하였다.
• 문제 해결에는 문제없었지만 N이 커지면 문제가 생길 수 있다.

...		
		int max = -1;
		for (int i = 0; i <= N - M; ++i)
		{
			for (int j = 0; j <= N - M; ++j)
			{
				int numFly = 0;
				for (int k = 0; k < M; ++k)
				{
					for (int m = 0; m < M; ++m)
					{
						numFly += fly[i + k][j + m];
					}
				}
				
				if (max < numFly)
				{
					max = numFly;
				}
			}
		}
...

---

Approach 2 ⭕

• 브루트포스가 아닌 누적 합을 이용하여 풀이하는 방식으로 수정하였다.
• 이와 유사한 문제를 다음에 만나면 브루트포스를 생각하기 보다는 누적 합 방식을 한번 고려해봐야 겠다.

---

Solution 💡

#include<iostream>
#include<vector>

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, M;

		cin >> N >> M;

		vector<vector<int>> fly(N, vector<int>(N));
		vector<vector<int>> prefixSum(N + 1, vector<int>(N + 1, 0));
		for (int i = 0; i < N; ++i)
		{
			for (int j = 0; j < N; ++j)
			{
				cin >> fly[i][j];
				prefixSum[i + 1][j + 1] = fly[i][j] + prefixSum[i][j + 1] + prefixSum[i + 1][j] - prefixSum[i][j];

			}
		}

		int max = -1;
		for (int i = M; i <= N; ++i)
		{
			for (int j = M; j <= N; ++j)
			{
				if (prefixSum[i][j] + prefixSum[i - M][j - M] - prefixSum[i - M][j] - prefixSum[i][j - M] > max)
				{
					max = prefixSum[i][j] + prefixSum[i - M][j - M] - prefixSum[i - M][j] - prefixSum[i][j - M];
				}
			}
		}

		cout << "#" << test_case << ' ' << max << '\n';
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

---

Reference 📄

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PzOCKAigDFAUq