백준 17135번 캐슬 디펜스 - C++ 풀이

 

---

 

1. 먼저 궁수 3명의 타깃을 계산만 한 뒤, 모아서 한 번에 죽인다.
2. 모든 적을 한 칸 내린다. (대신 궁수를 한 칸 올려도 된다.)
3. 1, 2번 과정을 N-1번 반복한다.

 

1. 먼저 궁수 3명의 타겟을 계산만 한 뒤, 모아서 한 번에 죽인다.

 궁수끼리 적이 중복될 수 있다. 따라서 타겟을 계산하고 바로 죽이면 안 되고, 궁수 3명의 타깃을 일단 계산만 한 뒤에 3개의 타깃을 한 번에 죽여야 한다. 타깃 계산은 거리가 가까운 순으로, 거리가 가깝다면 왼쪽에 있는 순으로 반복문을 이용해서 간단하게 구현하였다.

 

2. 모든 적을 한 칸 내린다. (대신 궁수를 한 칸 올려도 된다.)

 모든 적을 한 칸 내린다. 대신 궁수를 한칸 올려도 똑같은 상황이기 때문에 아래 코드에서는 궁수를 올려주었다. 다만 궁수를 올리도록 구현하는 경우 타깃 계산을 할 때에 궁수 아래쪽은 탐색하지 않도록 처리해주어야 한다.

 

3. 1, 2번 과정을 N-1번 반복한다.

 매 라운드마다 적이 한 칸씩 내려오므로 총 N-1번의 라운드를 시뮬레이션해야한다.

반응형

---

#include <iostream>
#include <string.h>
#include <vector>

using namespace std;

typedef pair<int, int> pii;
const int ENEMY = 1;
const pii NO_TARGET = {-1, -1};

int N, M, D;
int board[15][15];
bool isDead[15][15];

// calcTarget(r, c): r, c 위치에 있는 궁수의 타겟 계산
pii calcTarget(int r, int c) {
    for (int d = 1; d <= D; d++) {
        for (int dc = -(d-1); dc <= (d-1); dc++) {
            int dr = -(d - abs(dc));
            int er = r + dr;
            int ec = c + dc;
            if (er < 0 || er >= N || ec < 0 || ec >= M) continue;
            
            if (board[er][ec] == ENEMY && !isDead[er][ec]) {
                return {er, ec};
            }
        }
    }
    
    return NO_TARGET;
}

int simulate(int archer1, int archer2, int archer3) {
    int killCnt = 0;
    vector<int> archers = {archer1, archer2, archer3};
    
    memset(isDead, 0, sizeof(isDead));
    
    // 적을 한 칸 내리는 대신 궁수를 한 칸 올림
    for (int i=N; i>0; i--) {
        vector<pii> targets;
        
        for (auto archer: archers) {
            targets.push_back(calcTarget(i, archer)); 
        }
        
        // 적 모아서 한번에 처리
        for (auto target: targets) {
            if (target == NO_TARGET) continue;
            
            int r = target.first;
            int c = target.second;
            
            if (!isDead[r][c]) killCnt++;
            isDead[r][c] = true;
        }
    }
    
    return killCnt;
}

int solution(){
    int maxKill = 0;
    
    for (int i=0; i<M-2; i++) {
        for (int j=i+1; j<M-1; j++) {
            for (int k=j+1; k<M; k++) {
                maxKill = max(maxKill, simulate(i, j, k));
            }
        }
    }
    
    return maxKill;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M >> D;
    for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            cin >> board[i][j];
        }
    }
    
    cout << solution();

    return 0;
}