백준 32715: 십자가 찾기

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

 

 

십자가의 중심이 되는 점을 찾고자 한다.

가로줄을 전부 순회하면서 한 점을 중심으로 좌우로 연속으로 2K+1개 칸이 색칠되어 있는 것들을 찾아 십자가 중심의 후보로 넣는다.

세로줄도 똑같이 순회하면서 후보를 찾는다.

이때 겹치는 것이 십자가의 중심이 된다.

 

특정 점을 중심으로 가로로도 세로로도 2K+1개 칸이 색칠되어 있는 점을 말하는 거다.

 

#include <iostream>

using namespace std;
typedef long long ll;




int main()
{
    ll n,m,k;
    cin>>n>>m>>k;
    int a[3100][3100];//색칠 여부를 배열로 저장
    ll ans=0;
    for(ll i=0;i<n;i++)
    {
        for(ll j=0;j<m;j++)
        {
            cin>>a[i][j];
        }
    }
    ll hubo[3100][3100]={0};//정답 후보를 저장
    
    for(ll i=0;i<n;i++)//각 가로줄 먼저 순회
    {
        ll count=0;//연속해서 색칠된 칸의 개수
        for(ll j=0;j<m;j++)
        {
            if(a[i][j]==1)
            {
                count++;//색칠된 칸을 만날 때마다 1씩 더한다
                if(count>=(2*k+1))//연속 색칠된 칸이 2K+1이 된 경우
                {
                    hubo[i][j-k]=1;//그 중앙에 있는 점은 정답 후보가 된다
                }
            }
            else
            {
                count=0;//색칠 안 된 칸을 만나면 count를 0으로 초기화한다
            }
        }
    }
    for(ll j=0;j<m;j++)//세로줄 순회
    {
        ll count=0;//가로줄과 논리는 똑같다.
        
        for(ll i=0;i<n;i++)
        {
            if(a[i][j]==1)
            {
                count++;
                if(count>=(2*k+1))
                {
                    if(hubo[i-k][j]==1)//세로줄에서 찾은 후보가 가로줄에서도 후보라면?
                    {
                        ans++;//그 칸은 정답에 포함된다
                    }
                    
                }
            }
            else
            {
                count=0;
            }
        }
    }
    cout<<ans;
    return 0;
}

 

모든 칸을 하나하나 다 검사하면 시간복잡도가 아주 커진다. 따라서 이 코드는 누적합의 논리를 이용했다.