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

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.


N*N 크기의 도시에 홈방범 서비스를 제공하려고 한다.

홈방범 서비스는 운영 상의 이유로 [Fig. 1]의 파란색 부분과 같이 마름모 모양의 영역에서만 제공된다.

[Fig. 1]

또한, 홈방범 서비스를 제공하기 위해서는 운영 비용이 필요하다.

[Fig. 2]와 같이 서비스 영역의 크기 K 가 커질수록 운영 비용이 커진다.

운영 비용은 서비스 영역의 면적과 동일하며, 아래와 같이 구할 수 있다.

운영 비용 = K * K + (K - 1) * (K - 1)

운영 영역의 크기 K 는 1 이상의 정수이다.

 - K = 1 일 때, 운영 비용은 1 이다.

 - K = 2 일 때, 운영 비용은 5 이다.

 - K = 3 일 때, 운영 비용은 13 이다.

 - K = 4 일 때, 운영 비용은 25 이다.

 

[Fig. 2]

[Fig. 3]과 같이 도시를 벗어난 영역에 서비스를 제공해도 운영 비용은 변경되지 않는다.

[Fig. 3]의 경우 K = 3 이므로, 운영 비용은 13 이다.
 

 [Fig. 3]

홈방범 서비스를 제공받는 집들은 각각 M의 비용을 지불할 수 있어, 보안회사에서는 손해를 보지 않는 한 최대한 많은 집에 홈방범 서비스를 제공하려고 한다.

도시의 크기 N과 하나의 집이 지불할 수 있는 비용 M, 도시의 정보가 주어진다.

이때, 손해를 보지 않으면서 홈방범 서비스를 가장 많은 집들에 제공하는 서비스 영역을 찾고,

그 때의 홈방범 서비스를 제공 받는 집들의 수를 출력하는 프로그램을 작성하라.


[예시]

예를 들어, [Fig. 4]과 같이 N이 8인 도시의 정보가 주어지고, 하나의 집이 지불할 수 있는 비용 M이 3이라고 생각해 보자.

 

[Fig. 4]

[Fig. 5]와 같이 서비스 영역 K = 2로 하여 홈방범 서비스를 제공할 때는 최대 3개의 집까지 서비스 제공이 가능하다.

이 경우 보안회사의 이익은 4가 되어 손해를 보지 않고 서비스 제공이 가능하다.

보안회사의 이익(4) = 서비스 제공받는 집들을 통해 얻는 수익(3*3) - 운영 비용(5)

 

[Fig. 5]

[Fig. 6]은 서비스 영역 K = 3으로 하여 홈방범 서비스를 제공할 때에 최대 5개의 집까지 서비스 제공이 가능한 경우 중 하나이다.

보안회사의 이익(2) = 서비스 제공받는 집들을 통해 얻는 수익(3*5) - 운영 비용(13)
 

[Fig. 6]

위의 예에서, 보안회사가 손해를 보지 않고 서비스 가능한 최대 집의 수는 5이며, 5가 정답이 된다.


[제약사항]

1. 시간제한 : 최대 50개 테스트 케이스를 모두 통과하는데, C/C++/Java 모두 3초

2. 도시의 크기 N은 5 이상 20 이하의 정수이다. (5 ≤ N ≤ 20)

3. 하나의 집이 지불할 수 있는 비용 M은 1 이상 10 이하의 정수이다. (1 ≤ M ≤ 10)

4. 홈방범 서비스의 운영 비용은 서비스 영역의 면적과 동일하다.

5. 도시의 정보에서 집이 있는 위치는 1이고, 나머지는 0이다.

6. 도시에는 최소 1개 이상의 집이 존재한다.


[입력]

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 도시의 크기 N과 하나의 집이 지불할 수 있는 비용 M이 주어진다.

그 다음 줄부터 N*N 크기의 도시정보가 주어진다. 지도에서 1은 집이 위치한 곳이고, 나머지는 0이다.


[출력]

테스트 케이스의 개수만큼 T줄에 T개의 테스트 케이스 각각에 대한 답을 출력한다.

각 줄은 "#x"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (x는 1부터 시작하는 테스트 케이스의 번호이다)

출력해야 할 정답은 손해를 보지 않으면서 홈방범 서비스를 가장 많은 집들에 제공하는 서비스 영역을 찾았을 때,

그 때의 서비스를 제공 받는 집들의 수이다.

 

 

 

문제가 좀 헷갈리게 내놨다. 이익이 0이어도 회사는 서비스를 한다. <- 이 조건에 대한 설명이 좀 애매하지 않았나 싶다.

 

#include <iostream>
#include <vector>
 
using namespace std;
 
int n,m,ans;
 
bool MAP[20][20];
vector<pair<int, int> > house;
 
int abs(int a, int b)
{
    return a > b ? a - b : b - a;
}
int cost(int k)
{
    return k*k + (k-1)*(k-1);
}
 
bool check(int a, int b, int len)
{
    int cnt = 0;
 
    for(int i=0;i<house.size();i++)
        if(abs(a, house[i].first) + abs(b, house[i].second) < len)
            cnt++;
 
    if(cnt * m - cost(len) >= 0 && cnt > ans)
    {
        ans = cnt;
        return true;
    }
    return false;
}
void solve(int MAX)
{
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            for(int a = n + 2;a>0;a--)
            {
                if(check(i,j,a)) break;
                if(ans == MAX) return;
            }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tc, cnt;
    cin>>tc;
    for(int t=1;t<=tc;t++)
    {
        ans = 0,cnt = 0;
        house.clear();
        cin>>n>>m;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
            {
                cin>>MAP[i][j];
                if(MAP[i][j])
                {
                    house.push_back({i,j});
                    cnt ++;
                }
            }
 
        solve(cnt);
        cout<<'#'<<t<<' '<<ans<<'\n';
    }
    return 0;
}
 

처음에 bfs를 썼지만 참담하게(?) 시간 초과

생각해보니 굳이 bfs를 쓰지 않고 집의 좌표를 저장해 놨다가 거리를 구해 비교하면 되겠다 싶어 해봤더니 바로 통과.

 

여러번 해야하니 백터는 clear로 초기화 해준다.

1. 입력을 받으면서 벡터에 집의 좌표들을 저장해 놓는다.

2. 모든 지점에 대해 거리가 n + 2 인곳 부터 손해를 보지 않는지 체크

3. 손해를 본다면 true를 리턴해 해당 좌표는 그만하게 함

4. 만약 ans 가 총 집의 개수와 같다면 종료