BOJ 1286 : 부분 직사각형

• 문제 링크 : boj.kr/1286
• 난이도 : G5
• 태그 : 조합론

1286번: 부분 직사각형

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, m;
    cin >> n >> m;
    vector<ll> arr(26);
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for(int j = 0; j < m; j++) {
            int u = i+1;
            int d = n-i;
            int l = j+1;
            int r = m-j;
            arr[s[j]-'A'] += (u+n)*d*(l+m)*r;
            arr[s[j]-'A'] += (u+n)*d*l*(r+m);
            arr[s[j]-'A'] += u*(d+n)*(l+m)*r;
            arr[s[j]-'A'] += u*(d+n)*l*(r+m);
        }
    }

    for(auto u : arr) cout << u << "\n";

    return 0;
}

---

풀이

부분 직사각형 안의 문자를 세는 것이 아니라, 한 문자가 몇 개의 부분 직사각형에 포함되는지를 세어보자.

직사각형의 크기가 N*M, 어떤 문자의 좌표를 (i,j)라고 할 때, 포함되는 직사각형의 수는 (i+1)*(j+1)*(n-i)*(m-j)이다.

직사각형이 2 by 2로 확장되므로 이에 맞춰서 4가지 경우를 세어 주면 된다.