17135

• implementation

적들의 초기 위치가 주어지고
세 궁수가 라운드마다 전진하는 적들 중

사정거리에 들어오면서,
가장 가까우면서,
가장 좌측에 있는 적을 공격합니다.

궁수들은 같은 적을 공격할 수 있으며
궁수가 위치한 지역까지 살아 남은 적은
공격 실패로 간주하여 카운트하지 않습니다.

최적의 궁수 배치를 알 수 없기 때문에
순열을 이용한 조합을 이용해 각 배치 케이스를 만들고
각 배치 케이스 마다의 계산 결과값 중

최대값을 답으로 제출합니다.

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

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;

const int inf = ((1 << 31) - 1);

void init_archers_and_selector(int row_len, int col_len, 
                               vector<pi>& archers, vector<int>& selector) {
    for (int i = 0; i < col_len; i++) {
        archers.push_back({i, row_len});
        selector.push_back(i >= col_len - 3);
    }
}

void init_enemies(int row_len, int col_len, vector<pi>& enemies) {
    for (int i = 0; i < row_len; i++)
        for (int j = 0; j < col_len; j++) {
            int is_exist;
            cin >> is_exist;
            if (is_exist)
                enemies.push_back({j, i});
        }

    sort(enemies.begin(), enemies.end());
}

int calc_dist(pi enemy, pi archer) {
    return abs(enemy.second - archer.second) + abs(enemy.first - archer.first);
}

pi shoot(int max_range, pi enemy, pi archer) {
    int dist = calc_dist(enemy, archer);
    return {dist <= max_range, dist};
}

int shoot_the_closest_enemy(int max_range, vector<pi> enemies, pi archer) {
    int enemy_count = (int) enemies.size(),
        min_dist = inf;

    for (int i = 0; i < enemy_count; i++) {
        pi result = shoot(max_range, enemies[i], archer);
        
        int is_succeed = result.first,
            dist = result.second;

        if (is_succeed && min_dist > dist)
            min_dist = dist;
    }
    
    for (int i = 0; i < enemy_count; i++) {
        pi result = shoot(max_range, enemies[i], archer);
        
        int is_succeed = result.first,
            dist = result.second;
        
        if (is_succeed && min_dist == dist)
            return i;
    }

    return -1;
}

vector<pi> extract_enemies(vector<pi> enemies, set<int> indexes) {
    int enemy_count = (int) enemies.size();

    vector<pi> extracted_enemies;

    for (int i = 0; i < enemy_count; i++)
        if (indexes.find(i) == indexes.end())
            extracted_enemies.push_back(enemies[i]);

    return extracted_enemies;
}

void move_enemies(vector<pi>& enemies) {
    vector<pi> moved_enemies;

    for (pi enemy : enemies)
        moved_enemies.push_back({enemy.first, enemy.second + 1});
    
    enemies = moved_enemies;
}

vector<pi> remove_out_of_bound_enemies(int row_len, vector<pi> enemies) {
    vector<pi> removed_enemies;

    for (pi enemy : enemies)
        if (enemy.second < row_len)
            removed_enemies.push_back(enemy);

    return removed_enemies;
}

int calc_ans_to_a_specific_case(int row_len, int max_range, 
                                vector<pi> enemies, vector<pi> archers) {
    int archer_count = (int) archers.size(),
        ans = 0;

    while (1) {
        set<int> indexes;

        for (int i = 0; i < archer_count; i++) {
            int index = shoot_the_closest_enemy(max_range, enemies, archers[i]);

            if (index != -1)
                indexes.insert(index);
        }

        ans += (int) indexes.size();

        vector<pi> extracted_enemies = extract_enemies(enemies, indexes);
        swap(enemies, extracted_enemies);

        if (enemies.empty())
            break;

        move_enemies(enemies);

        vector<pi> removed_enemies = remove_out_of_bound_enemies(row_len, enemies);
        swap(enemies, removed_enemies);
        
        if (enemies.empty())
            break;
    }

    return ans;
}

vector<pi> extract_archers(int col_len, vector<pi> archers, vector<int> selector) {
    vector<pi> extracted_archers;

    for (int i = 0; i < col_len; i++)
        if (selector[i])
            extracted_archers.push_back(archers[i]);

    return extracted_archers;
}

int calc_ans(int row_len, int col_len, int max_range, 
             vector<pi> enemies, vector<pi> archers, vector<int> selector) {
    int ans = 0;

    do {
        ans = max(
            calc_ans_to_a_specific_case(
                row_len, max_range, enemies, 
                extract_archers(col_len, archers, selector)
            ), ans);
    }
    while (next_permutation(selector.begin(), selector.end()));

    return ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int row_len, col_len, max_range;
    cin >> row_len >> col_len >> max_range;

    vector<pi> archers;
    vector<int> selector;

    init_archers_and_selector(row_len, col_len, archers, selector);

    vector<pi> enemies;

    init_enemies(row_len, col_len, enemies);

    cout << calc_ans(row_len, col_len, max_range, enemies, archers, selector);

    return 0;
}