SWEA 2117 [모의 SW 역량테스트] 홈 방범 서비스 C++

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu 

SW Expert Academy

 

최종 코드

• GitHub -> https://github.com/hwayeon351/SWEA-Algorithms/blob/main/SWEA2117.cpp

GitHub - hwayeon351/SWEA-Algorithms: SWEA 알고리즘 소스 코드 모음

//
//  main.cpp
//  SWEA2117
//
//  Created by Hwayeon on 2021/10/21.
//

#include <iostream>
using namespace std;

int N, M;
int city[21][21] = {0, };
int house = 0;
int max_house = 0;

void service(int sx, int sy, int K){
    int cnt = 0;
    int d = 0;
    for(int y=sy; y<sy+K; y++){
        for(int dx=-d; dx<=d; dx++){
            int nx = sx+dx;
            if(nx<0 || nx>=N || y<0 || y>N) continue;
            cnt += city[y][nx];
        }
        d++;
    }
    d-=2;
    for(int y=sy+K; y<sy+2*K-1; y++){
        for(int dx=-d; dx<=d; dx++){
            int nx = sx+dx;
            if(nx<0 || nx>=N || y<0 || y>N) continue;
            cnt += city[y][nx];
        }
        d--;
    }
    if(cnt*M < K*K+(K-1)*(K-1)) return;
    if(cnt > max_house) max_house = cnt;
}

void get_service_area(){
    int K;
    if(N % 2) K = N;
    else K = N+1;
    
    for(int k=1; k<=K; k++){
        if(k*k+(k-1)*(k-1) > M*house) continue;
        for(int y=(-2*K+2); y<N; y++){
            for(int x=-K; x<N+K; x++){
                service(x, y, k);
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    int test_case;
    int T;
    cin >> T;
    for(test_case=1; test_case<=T; ++test_case){
        house = 0;
        max_house = 0;
        cin >> N >> M;
        for(int y=0; y<N; y++){
            for(int x=0; x<N; x++){
                cin >> city[y][x];
                house += city[y][x];
            }
        }
        get_service_area();
        cout << "#" << test_case << " " << max_house << endl;
    }
    return 0;
}

---

풀이 과정

풀이 시간 1시간 18분

#include <iostream>
using namespace std;

int N, M;
int city[21][21] = {0, };

//도시 안의 집 수
int house = 0;

//홈방범 서비스를 제공 받는 최대 집 수
int max_house = 0;

void service(int sx, int sy, int K){
	//K영역에 속해 서비스를 제공받은 집 수
    int cnt = 0;
    
    //마름모 K 영역 탐색
    int d = 0;
    for(int y=sy; y<sy+K; y++){
        for(int dx=-d; dx<=d; dx++){
            int nx = sx+dx;
            //범위를 벗어난 경우, 무시한다
            if(nx<0 || nx>=N || y<0 || y>N) continue;
            cnt += city[y][nx];
        }
        d++;
    }
    d-=2;
    for(int y=sy+K; y<sy+2*K-1; y++){
        for(int dx=-d; dx<=d; dx++){
            int nx = sx+dx;
            //범위를 벗어난 경우, 무시한다
            if(nx<0 || nx>=N || y<0 || y>N) continue;
            cnt += city[y][nx];
        }
        d--;
    }
    //서비스 영역에 속한 집들이 지불한 비용이 운영 비용보다 적은 경우, 손해가 발생하므로 해당 경우는 무시한다
    if(cnt*M < K*K+(K-1)*(K-1)) return;
    //운영 비용에 손해가 없는 경우, max_house를 최댓값으로 갱신한다
    if(cnt > max_house) max_house = cnt;
}

void get_service_area(){
	//1. K 범위 정하기
    int K;
    //홀수인 경우, K는 N 이하의 범위에서 도시 전체에 서비스하는 모든 경우를 구할 수 있다
    if(N % 2) K = N;
    //짝수인 경우, K는 N+1 이하의 범위에서 도시 전체에 서비스하는 모든 경우를 구할 수 있다
    else K = N+1;
    
    //2. k에 대해 가능한 모든 운영 영역을 살펴본다
    for(int k=1; k<=K; k++){
    	//운영 비용이 각 집들이 지불하는 비용보다 큰 경우, 손해가 발생하므로 해당 운영 영역 K로 서비스할 수 없다
        if(k*k+(k-1)*(k-1) > M*house) continue;
      	
        for(int y=(-2*K+2); y<N; y++){
            for(int x=-K; x<N+K; x++){
            	//(x, y)를 시작으로 K영역 서비스를 제공한다
                service(x, y, k);
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    int test_case;
    int T;
    cin >> T;
    for(test_case=1; test_case<=T; ++test_case){
        house = 0;
        max_house = 0;
        cin >> N >> M;
        for(int y=0; y<N; y++){
            for(int x=0; x<N; x++){
                cin >> city[y][x];
                house += city[y][x];
            }
        }
        get_service_area();
        cout << "#" << test_case << " " << max_house << endl;
    }
    return 0;
}
//시간복잡도 = O(N^4), 공간복잡도 = O(N^2)