BOJ 3095

27 Apr 2020 • ProblemSolving

플러스의 개수

문제출처

문제 해석

  • 2차원 배열에 있는 플러스의 개수를 출력하는 문제입니다.
  • 플러스란 변의 길이가 1보다 큰 홀수인 정사각형으로 가운데 행과 열은 1로, 나머지는 0으로 채워져있습니다.

설계(10)

  • 주어진대로 구현만 하면 되는 문제입니다.
  • 처음에 생각하기를 플러스를 찾기위해서 모든 행열을 탐색하고O(N^2),1인 곳에서 상하좌우로 1이고 나머지 부분은 0인것을 탐색O(N^2)하려면 O(N^4)으로 무조건 시간초과가 날 것으로 예상했습니다.
  • 플러스인지 탐색하는 부분을 O(N)으로 최적화시켜도 O(N^3)이므로 부족하다고 생각했습니다.
  • 최적화하기 위해서 누적합기능을 구현하였습니다.
  • 가운데 행과 열은 탐색은 하되 나머지부분이 0인 것을 체크하기 위해서 미리 누적합을 만들어놨습니다.
  • (x-cnt,y-cnt)~(x+cnt,y+cnt) 범위가 플러스인지 확인하기 위해서 가운데 기준 상하좌우의 값을 확인후, 누적합으로 원하는 1의 개수가 맞는지 체크합니다.

구현(20)

코드
#include <iostream>
using namespace std;

#define MAXN 2001

int map[MAXN][MAXN];
int psum[MAXN][MAXN];
int N;
bool is_range(int x, int y){
    return (x>=1 && y>=1 && x <=N && y<=N);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    for (int i = 1; i <=N ;i++){
        for (int j = 1; j<=N; j++){
            char tmp;
            cin >> tmp;
            map[i][j] = tmp-'0';
            psum[i][j] = psum[i-1][j] +psum[i][j-1]-psum[i-1][j-1]+map[i][j];
        }
    }
    int ans = 0;
    for (int i = 2; i<N; i++){
        for (int j= 2;j <N; j++){
            if (map[i][j] && map[i-1][j] && map[i+1][j] && map[i][j-1] && map[i][j+1]){
                int cnt = 2;
                int sum = 5;
                ans++;
                while (is_range(i-cnt,j-cnt)||is_range(i+cnt,j+cnt)){
                    if (map[i-cnt][j] && map[i+cnt][j] && map[i][j-cnt]&&map[i][j+cnt]&& (psum[i+cnt][j+cnt]-psum[i-cnt-1][j+cnt]-psum[i+cnt][j-cnt-1]+psum[i-cnt-1][j-cnt-1] == sum+4)) {
                        sum+=4;
                        ans++;
                        cnt++;
                    }
                    else break;
                }
            }
        }
    }
    cout << ans <<"\n";
    return 0;
}
디버깅
제출결과
  • 84 ms

마무리

  • 완전탐색문제였습니다. 누적합같은 최적화를 하지 않아도 시간안에 통과가 가능한 모양입니다.
 BOJ

Related Posts