C++로 N×N 이진 행렬에서 만들 수 있는 1의 최대 개수 구하기

문제 개요

이 문제는 주어진 제약 조건을 만족하는 이진 행렬에 포함시킬 수 있는 1의 최대 개수를 구하는 것입니다.

두 정수 N과 X가 주어지며(단, X ≤ N), 행렬의 크기는 N×N이어야 하고, 크기가 X×X인 모든 부분 행렬에는 최소한 하나의 0이 포함되어야 합니다.

예제를 통해 문제를 자세히 살펴보겠습니다.

입력 − N=4, X=2

출력 − 12

설명 − 결과 행렬은 다음과 같습니다.

1 1 1 1
1 0 0 1
1 0 0 1
1 1 1 1

입력 − N=7, X=3

출력 − 45

접근 방법

• 1의 개수를 최대화하려면 먼저 행렬에 배치해야 하는 0의 최소 개수를 구해야 합니다.

  여러 행렬에서 공통적으로 나타나는 패턴을 관찰해 보면, 필요한 0의 개수는 (N / X)²임을 알 수 있습니다. 즉, 가로와 세로 방향으로 각각 X 간격마다 0을 배치하면 어떤 X×X 부분 행렬을 선택하더라도 반드시 그 안에 0이 하나 이상 포함되게 됩니다.

  따라서 1의 최대 개수 = 행렬의 전체 원소 수 − 0의 개수입니다.

• MaxOne() 함수 안에서 int형 변수 Z를 선언하고, 필요한 0의 최소 개수인 (N / X)² 값을 저장합니다.

• 그다음 행렬의 전체 크기를 저장하기 위해 int형 변수 total = N * N을 초기화합니다.

• 마지막으로 최종 답을 저장할 int형 변수 ans = total − Z를 초기화한 뒤 ans를 반환합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
int MaxOne(int N, int X){
    // 필요한 0의 최소 개수
    int Z = (N / X);
    Z = Z * Z;
    /* 행렬의 전체 원소 수 = 행렬 크기의 제곱 */
    int total = N * N;
    // 최종 답
    int ans = total - Z;
    return ans;
}
int main(){
    int N = 4;
    int X = 2;
    cout << MaxOne(N, X);
    return 0;
}

출력 결과

위 코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다.

12

N=4, X=2인 경우 전체 원소는 16개이고, 필요한 0의 최소 개수는 (4/2)² = 4개이므로 1의 최대 개수는 16 − 4 = 12개가 됩니다. 이 알고리즘은 단순한 산술 연산만 사용하므로 시간 복잡도는 O(1)로 매우 효율적입니다.