문제 소개
크기가 w × h인 행렬 M이 있다고 가정해 보겠습니다. 행렬의 모든 칸은 0 또는 1의 값을 가지며, 크기가 l × l인 임의의 정사각형 부분 행렬(sub-matrix)은 최대 maxOnes개의 1만 포함할 수 있습니다. 이러한 조건을 만족하면서 행렬 M 전체가 가질 수 있는 1의 최대 개수를 구하는 것이 이번 문제의 목표입니다.
예시
입력이 w = 3, h = 3, l = 2, maxOnes = 1이라면 출력은 4가 됩니다. 3 × 3 행렬 안에서 어떤 2 × 2 부분 행렬도 1을 두 개 이상 가질 수 없기 때문입니다. 1을 4개 배치한 최적의 해는 다음과 같습니다.
| 1 | 0 | 1 |
| 0 | 0 | 0 |
| 1 | 0 | 1 |
해결 접근 방법
이 문제의 핵심 아이디어는 주기성(periodicity)입니다. 좌표 (i, j)의 값은 (i mod n, j mod n) 위치의 패턴에 의해 결정되므로, n × n 크기의 기본 패턴 안에서 각 칸이 실제 행렬 전체에서 몇 번 등장하는지 세면 됩니다. 그다음 등장 횟수가 많은 순서대로 maxOnes개의 칸을 선택해 1을 채우면 전체 1의 개수가 최대화됩니다.
구체적인 단계는 다음과 같습니다.
- 결괏값을 저장할 변수 ret을 0으로 초기화합니다.
- n × n 크기의 2차원 배열 sq를 생성합니다.
- i가 height보다 작은 동안 반복하고, 그 안에서 j가 width보다 작은 동안 반복하며 sq[i mod n][j mod n]의 값을 1씩 증가시킵니다. 이렇게 하면 각 패턴 칸이 전체 행렬에서 차지하는 빈도를 계산할 수 있습니다.
- 배열 v를 정의하고, sq의 모든 원소를 v에 순서대로 삽입합니다.
- v를 내림차순으로 정렬합니다.
- i와 j를 0부터 시작해 i가 v의 크기보다 작고 j가 maxOnes보다 작은 동안 반복하며 ret에 v[i]를 더합니다.
- 최종적으로 ret을 반환합니다.
C++ 구현 예제
아래 코드를 통해 위 알고리즘이 실제로 어떻게 동작하는지 확인해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maximumNumberOfOnes(int width, int height, int n, int maxOnes) {
int ret = 0;
vector < vector <int> > sq(n, vector <int>(n));
for(int i = 0; i < height; i++){
for(int j = 0; j < width; j++){
sq[i % n][j % n]++;
}
}
vector <int> v;
for(int i = 0; i < n; i++){
for(int j = 0; j < n ; j++){
v.push_back(sq[i][j]);
}
}
sort(v.rbegin(), v.rend());
for(int i = 0, j = 0; i < v.size() && j < maxOnes; i++, j++){
ret += v[i];
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.maximumNumberOfOnes(3,3,2,1));
}입력
3, 3, 2, 1
출력
4
동작 원리 정리
위 코드에서 첫 번째 이중 반복문은 전체 행렬의 각 좌표를 n으로 나눈 나머지 위치에 카운트를 누적합니다. 예를 들어 3 × 3 행렬에서 n = 2라면, (0,0) 패턴 칸은 4번, (0,1)과 (1,0)은 각각 2번, (1,1)은 1번 등장하게 됩니다. 이후 카운트를 내림차순 정렬해 상위 maxOnes개의 값을 더하면, 제약 조건을 위반하지 않으면서 얻을 수 있는 1의 최대 개수를 효율적으로 계산할 수 있습니다. 시간 복잡도는 O(w·h + n² log n)으로 매우 효율적입니다.