백준 32176번 - 통신 시스템의 성능 저하(C++)

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

첫 풀이론 bfs를 통해 가장 가까운 K 개를 찾으려 했다. 경로 손실은 적을수록 좋기 때문이다. 그러나, 결국 이 방식도 K1 개의 모든 경우를 조합해보는 것과 다를바가 없다.

그래서 이 문제는 최적화된 브루트포스가 정답이다.

문제 조건을 봤을 때,

 

Ex) N = 4, M = 14이면,

 

K1 = 10, 11, 12, 13, 14 중 하나가 된다. 그리고 가능한 경우의 수는

 

14 combination 10, 14 combination 11, 14 combination 12, 14 combination 13, 14 combination 14

 

조합의 성질에 따라

 

14 combination 4, 14 combination 3, 14 combination 2, 14 combination 1, 14 combination 0

 

으로 최적화가 가능하다. 위의 방식은 아주 많은 경우의 수를 찾아야하기 때문에 TLE가 발생한다.

 

즉, 아침일 땐 M combination (M - K1) 을, 저녁일 땐 M combination K2 를 하면 되는 문제이다. 이 발상을 하기가 어려웠다. 만약 조건이 K1 의 범위가 0부터 M까지 였다면 이 방법을 사용할 수 없었다. 그러나 범위를 제한을 두었기 때문에 최적화할 수 있는 문제였다. 완전탐색 범위를 최적화하는 아이디어를 얻을 수 있었던 좋은 문제였고 문제가 아닌 범위에서 힌트를 얻을 수도 있다는 생각이 들었다.

 

#include <iostream>
#include <vector>
using namespace std;

vector<pair<int, int>> nodes;
bool check[36];
int N, M, K1, K2;
int s_x, s_y;
int distStation(int x, int y){
    return abs(x - s_x) + abs(y - s_y);
}

int answer = 0;

void dfs(int idx, int cnt, int lim, bool day){
    if(cnt == lim){
        int P = 0, U, C;
        int x1 = 10, y1 = 10, x2 = 0, y2 = 0;
        for(int i = 0; i < nodes.size(); i++){
            if(day) {
                if(!check[i]){
                P += distStation(nodes[i].first, nodes[i].second);
                x1 = min(x1, nodes[i].first);
                y1 = min(y1, nodes[i].second);
                x2 = max(x2, nodes[i].first);
                y2 = max(y2, nodes[i].second);
            }     
            }else{
                if(check[i]){
                P += distStation(nodes[i].first, nodes[i].second);
                x1 = min(x1, nodes[i].first);
                y1 = min(y1, nodes[i].second);
                x2 = max(x2, nodes[i].first);
                y2 = max(y2, nodes[i].second);
            }     
            }       
        }
        U = (abs(x1 - x2) + 1) * (abs(y1 - y2) + 1);
        C = max(P - U, 0);
        answer = max(answer, C);        
        return;
    }

    for(int i = idx; i < nodes.size(); i++){
        if(check[i]) continue;

        check[i] = true;
        dfs(i, cnt + 1, lim, day);
        check[i] = false;
    }
}

int main(){
    cin >> N >> M >> K1 >> K2;

    for(int i = 0; i < N; i++){
        string str; cin >> str;
        for(int j = 0; j < N; j++){
            if(str[j] == 'N'){
                nodes.push_back({i, j});
            }else if(str[j] == 'B'){
                s_x = i;
                s_y = j;
            }
        }
    }

    dfs(0, 0, M - K1, true);    
    cout << answer << '\n';
    answer = 0;
    dfs(0, 0, K2, false);
    cout << answer << '\n';
}