[SWEA] 2117번 홈 방범 서비스

2117번 홈 방범 서비스

문제 링크

 

해결방법

모든 경우를 탐색해보는 완전탐색 문제이다

 

 

⭐️ 솔루션 ⭐️

SWEA 홈페이지에서 솔루션을 참고했다 ㅠㅠ

• 마름모를 만들지 않고, 두 점 사이의 거리의 비교를 통해 확인할 수 있다
• k ≤ n+2 의 의미는 모든 맵을 포함하는 경우까지 k를 증가시켜야 한다는 뜻이다

 

문제의 조건

• K : 서비스 영역 크기
• 운영 비용 : k * k + (k-1) * (k-1)
• M : 하나의 집이 낼 수 있는 비용
• 이익 : 집의 수 * M - 운영 비용

 

시간 복잡도

k는 1~n+2 까지 만들 수 있고, 각 k 마다 모든 노드를 탐색한다 (n^2)

해당 노드를 기점으로 마름모를 생성(n^2) 하여 최대 집의 수를 계산한다

따라서, 시간복잡도는 O(n^5) = 3,200,000 를 가진다

 

 

소스코드

문제 해결 시간 : 1h 10m

메모리 : 12624 KB

시간 : 788 ms

#include <iostream>
#include <cstring>
#include <math.h>
#include <algorithm>
#define MAX 21
using namespace std;

int testcase;
int n,m,ans;

int map[MAX][MAX];

int getMaxHouse(int r,int c,int k){
    int house = 0;
    
    for(int i=r-k+1; i<=r+k-1; i++){
        for(int j=c-k+1; j<=c+k-1; j++){
            // 맵 밖을 벗어나는 경우 제외
            if(i<0 || j<0 || i>=n || j>=n) continue;
            
            // 거리 계산
            int distance = abs(r-i) + abs(c-j);
            
            // 거리를 통해 마름모에 포함되는지 확인
            if(distance <= k-1 && map[i][j] == 1)
                house++;
        }
    }
    
    // 이익 계산
    int cost = house * m - ((k*k) + (k-1) * (k-1));
    
    // 손해가 아닌 경우, 집의 수 반환
    if(cost >= 0){
        return house;
    }else{
        return -1;
    }
}

void solve(int k){
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            // 마름모 생성 & 최대 집의 수 계산
            ans = max(ans,getMaxHouse(i,j,k));
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> testcase;
    for(int t=1; t<=testcase; t++){
        cin >> n >> m;
        
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                cin >> map[i][j];
            }
        }
        
        ans = 0;
        for(int k=1; k<=n+2; k++){
            solve(k);
        }
        
        cout << "#" << t << " " << ans << "\n";
    }
    
    return 0;
}