[백준] 3321 - 가장 큰 직사각형 (c++)

https://www.acmicpc.net/problem/3321

 

문제 요약

0또는1로 이루어진 N*M크기의 행렬이 주어진다. 열끼리 순서를 바꿀 수 있을 때 1로 이루어진 직사각형의 최대 넓이를 구해라.

 

풀이 (NM)

• DP
• 그리디

밑변 행을 고정시켜 보자. 모든 열에 대해 높이를 내림차순 배열로 갖고 있으면 순회하며 (i*현재 높이)를 모두 구해 최대 넓이를 구할 수 있다.

매번 퀵소트를 해주면 시간초과가 나기 때문에 O(N) 정렬 방식을 사용해야 한다. 직전 오름차순 배열에서 현재 값이 0이면 맨 뒤로 보내는 방법을 통해 정렬을 O(N)에 해결할 수 있다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define mid (st+en>>1)

int main() {
    cin.tie(0)->sync_with_stdio(0);cout.tie(0);
    int n,m;cin>>n>>m;
    ll ans=0;
    queue<short> l,r;
    for(int i=0;i<m;i++)
        l.push(i);
    vector<short> ar(m),dp(m);
    string str;
    for(int i=0;i<n;i++) {
        cin>>str;
        for(int j=0;j<m;j++)
            dp[j]=str[j]=='1'?dp[j]+1:0;
        
        for(int j=l.size();j;j--) {
            int x=l.front();l.pop();
            if(!dp[x])
                r.push(x);
            else
                l.push(x);
        }
        while(r.size())
            l.push(r.front()),r.pop();
        for(int j=0;j<m;j++) {
            int x=l.front();l.push(x),l.pop();
            ans=max(ans,(ll)dp[x]*(j+1));
        }
    }
    cout<<ans;
}