COFO::1238B Kill ‘Em all

• Link : COFO:1238B

Problem

• level : 1300
• tag : greedy, sortings
• TIME
  • to understand : 3
  • to algorithm : 5
  • to code : 2
  • to debug : 0
  • understaing edit : 0

Point

• 설명이 긴 문제입니다.
• 요약하면,
  • n개의 몬스터의 위치가 배열 a 로 주어집니다.
  • 각 몬스터는 1차원 직선상에 놓여있고 0보다 큰 좌표값을 가집니다.
  • 0이하의 좌표값으로 이동하게 되면 해당 몬스터는 죽습니다.
  • 이때, 매 턴마다 미사일이 optimal한 좌표에 떨어집니다.
  • 미사일이 떨어지는 좌표를 c라고 할때
    • c위치에 있던 몬스터는 모두 죽고
    • c < y 인 위치에 있던 몬스터는 모두 + r 만큼의 좌표로 이동하고
    • c > y 인 위치에 있던 몬스터는 모두 -r 만큼의 좌표로 이동합니다.
• 이때, 최소 몇턴만에 게임이 끝날지 예상합니다.

Design

• optimal이 어디일까 생각해보면 간단합니다.
• 살아있는 몬스터 중 최우측에 있는 녀석에게 미사일을 쏴야합니다.
• 그래야 걔는 죽고, 나머지 몬스터들은 모두 좌측으로 r칸씩 밀리기때문입니다.
• 그렇다면 이제 최우측부터 살펴보며 살아있는 몬스터들의 위치를 x - turn count * r 로 인식하여 턴 수를 계산하면 됩니다.

Complexity

• O(N)

Code

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define r_rep(i, a, b) for(int i=(a); i >(b); i--)
typedef long long ll;
using namespace std;

int n, r;
vector<int> a;
void solve(){
    cin >> n >> r;
    a.clear(); a.resize(n);
    rep(i, 0, n) cin >> a[i];
    sort(all(a));
    a.erase(unique(all(a)), a.end());
    
    int cnt = 0;
    n = sz(a);
    r_rep(i, n-1, -1){
        int v = a[i] - cnt * r;
        if(v <= 0) break;
        cnt++;
    }
    cout << cnt << '\n';
}
int main(){
    cin.tie(0);
    int tc; cin >> tc;
    while(tc--)
        solve();
    return 0;
}