토끼와 경주

https://www.codetree.ai/training-field/frequent-problems/problems/rabit-and-race/description?page=1&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

이동하는 도중 그 다음 칸이 격자를 벗어나게 된다면

방향을 반대로 바꿔 한 칸 이동하게 됩니다. 

어떻게 처리할까?

 

이 문제로 정확하게 알고 넘어가자!

일단 모듈러 연산을 한다. 

(얼마나 가야지 같은 방향 & 제자리로 가는가?)

go_down -> 아래, 위, 아래

 

<아래>

내려가는 것의 최댓값은 (n - rabbit.x)

그것보다 dist가 크면 dist에서 최대값을 빼고

rabbit.x = n 둔다.

dist가 작다면 + 하고 dist = 0

 

<위>

올라가는 것의 최대값은 (rabbit.x - 1)

그것보다 dist가 크면 dist에서 최대값을 빼고

rabbit.x = 1 둔다.

dist가 작다면 - 하고 dist = 0

 

<아래>

rabbit.x += dist;

 

우선순위로 이동할 토끼를 정한다고 쓰여있으니까

우선순위 큐를 이용하자.

우선순위 큐로 모든 것을 관리하면 안된다!

우선순위 큐는 top 말고

나머지는 정렬이 안되어있다.

 

토끼들의 정보들을 저장하는 배열을

각각 만들어서 하자.

 

출발하는 토끼를 결정하는 우선순위와

4방향 이동 후 어디로 갈지 & 보너스 토끼 결정

하는 우선순위가 다르다.

-> cmp 함수를 만들자.

 

 

<score 저장도 최적화>

이 테크닉은 많이 썼다.

O(N)으로 돌리면서

(r + c)를 더해주는 것이 아니라!

현재 뛴 토끼의 점수에

(r + c)를 빼준다.

그리고 total_sum += (r + c) 해준다.

 

토끼가 받은 점수 최대값 계산할 때

result[i] + total_sum

 

<소스 코드>

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <unordered_map>
 
using namespace std;
 
int n, m, p;
int k, bonus;
 
struct Rabbit {
    int x, y, j, id;
};
 
 
// 이동할 토끼 결정하는 pq 용 '<'
bool operator < (const Rabbit& a, const Rabbit& b)
{
    if (a.j == b.j)
    {
        if ((a.x + a.y) == (b.x + b.y))
        {
            if (a.x == b.x)
            {
                if (a.y == b.y)
                {
                    return a.id > b.id;
                }
                return a.y > b.y;
            }
            return a.x > b.x;
        }
        return (a.x + a.y) > (b.x + b.y);
    }
    return a.j > b.j;
}
 
// 가장 긴 위치를 판단하기 위한 정렬함수
bool cmp(Rabbit a, Rabbit b)
{
    if ((a.x + a.y) == (b.x + b.y))
    {
        if (a.x == b.x)
        {
            if (a.y == b.y)
            {
                return a.id < b.id;
            }
            return a.y < b.y;
        }
        return a.x < b.x;
    }
 
    return (a.x + a.y) < (b.x + b.y);
}
 
// id 값이 크니까 unordered_map
unordered_map<int, int> id_map;
 
// 뛴 토끼 알려주는 bool 배열
bool chk[2004];
 
// 각 토끼의 id
int r_id[2004];
 
// 각 토끼의 이동거리
int r_dist[2004];
 
// 각 토끼의 점프 횟수
int jump_cnt[2004];
 
// 각 토끼의 점수
long long score[2004];
 
// 각 토끼의 현재 위치
pair<int, int> wichi[2004];
 
long long total_sum;
 
// 아래
Rabbit Go_down(Rabbit cur, int dist)
{
    Rabbit down = cur;
    dist %= 2 * (n - 1);
 
    // 아래로
    if (dist >= n - down.x)
    {
        dist -= (n - down.x);
        down.x = n;
    }
    else
    {
        down.x += dist;
        dist = 0;
    }
 
    // 위로
    if (dist >= down.x - 1)
    {
        dist -= (down.x - 1);
        down.x = 1;
    }
    else
    {
        down.x -= dist;
        dist = 0;
    }
 
    down.x += dist;
 
    return down;
}
 
// 위
Rabbit Go_up(Rabbit cur, int dist)
{
    Rabbit up = cur;
    dist %= 2 * (n - 1);
 
    // 위로
    if (dist >= up.x - 1)
    {
        dist -= (up.x - 1);
        up.x = 1;
    }
    else
    {
        up.x -= dist;
        dist = 0;
    }
 
    // 아래로
    if (dist >= n - up.x)
    {
        dist -= (n - up.x);
        up.x = n;
    }
    else
    {
        up.x += dist;
        dist = 0;
    }
 
    up.x -= dist;
 
    return up;
}
 
// 왼쪽
Rabbit Go_left(Rabbit cur, int dist)
{
    Rabbit left = cur;
    dist %= 2 * (m - 1);
 
    // 왼쪽으로
    if (dist >= left.y - 1)
    {
        dist -= (left.y - 1);
        left.y = 1;
    }
    else
    {
        left.y -= dist;
        dist = 0;
    }
 
    // 오른쪽으로
    if (dist >= m - left.y)
    {
        dist -= (m - left.y);
        left.y = m;
    }
    else
    {
        left.y += dist;
        dist = 0;
    }
 
    left.y -= dist;
 
    return left;
}
 
Rabbit Go_right(Rabbit cur, int dist)
{
    Rabbit right = cur;
    dist %= 2 * (m - 1);
 
    if (dist >= m - right.y)
    {
        dist -= (m - right.y);
        right.y = m;
    }
    else
    {
        right.y += dist;
        dist = 0;
    }
 
    if (dist >= right.y - 1)
    {
        dist -= (right.y - 1);
        right.y = 1;
    }
    else
    {
        right.y -= dist;
        dist = 0;
    }
 
    right.y += dist;
 
    return right;
}
 
 
void start_round()
{
    priority_queue<Rabbit> pq;
 
    for (int i = 1; i <= p; i++)
    {
        chk[i] = false;
    }
 
    // 토끼들을 우선순위 큐에 넣는다
    for (int i = 1; i <= p; i++)
    {
        Rabbit tmp;
        tmp.x = wichi[i].first;
        tmp.y = wichi[i].second;
        tmp.j = jump_cnt[i];
        tmp.id = r_id[i];
 
        pq.push(tmp);
    }
 
    while (k--)
    {
        Rabbit cur = pq.top();
        pq.pop();
 
        int dist = r_dist[id_map[cur.id]];
        Rabbit tsugi = cur;
        tsugi.x = 0;
        tsugi.y = 0;
 
        // 토끼를 위, 아래, 왼쪽, 오른쪽 이동 시키고
        // 더 멀리 갈 수 있다면 tsugi로 설정
 
        Rabbit up_rabbit = Go_up(cur, dist);
        if (cmp(tsugi, up_rabbit))
            tsugi = up_rabbit;
 
        Rabbit down_rabbit = Go_down(cur, dist);
        if (cmp(tsugi, down_rabbit))
            tsugi = down_rabbit;
 
        Rabbit left_rabbit = Go_left(cur, dist);
        if (cmp(tsugi, left_rabbit))
            tsugi = left_rabbit;
 
        Rabbit right_rabbit = Go_right(cur, dist);
        if (cmp(tsugi, right_rabbit))
            tsugi = right_rabbit;
 
        // 점프 횟수 추가
        tsugi.j++;
        // pq에 push
        pq.push(tsugi);
 
        int tsugi_idx = id_map[tsugi.id];
        wichi[tsugi_idx] = make_pair(tsugi.x, tsugi.y);
        jump_cnt[tsugi_idx]++;
 
        // 달렸으니까 체크
        chk[tsugi_idx] = true;
 
        score[tsugi_idx] -= (tsugi.x + tsugi.y);
        total_sum += (tsugi.x + tsugi.y);
    }
 
    // 보너스 점수
    // 이번 경주 때 달려서 가장 멀리있는 토끼
    // pq에 토끼들이 다 저장되어있다
    Rabbit b_rabbit;
    b_rabbit.x = 0;
    b_rabbit.y = 0;
    while (!pq.empty())
    {
        Rabbit cur = pq.top();
        pq.pop();
 
        // 달리지 않은 토끼는 스킵
        if (!chk[id_map[cur.id]])
            continue;
 
        if (cmp(b_rabbit, cur))
            b_rabbit = cur;
    }
 
    score[id_map[b_rabbit.id]] += bonus;
}
 
void dist_change(int id, int t)
{
    int idx = id_map[id];
    r_dist[idx] *= t;
}
 
void print_ans()
{
    long long ans = 0;
    for (int i = 1; i <= p; i++)
        ans = max(ans, score[i] + total_sum);
 
    cout << ans;
}
 
int main()
{
    int q;
    cin >> q;
 
    while (q--)
    {
        int query;
        cin >> query;
 
        if (query == 100)
        {
            cin >> n >> m >> p;
            for (int i = 1; i <= p; i++)
            {
                cin >> r_id[i] >> r_dist[i];
                id_map[r_id[i]] = i;
                wichi[i] = make_pair(1, 1);
            }
        }
        else if (query == 200)
        {
            cin >> k >> bonus;
            start_round();
        }
        else if (query == 300)
        {
            int id, t;
            cin >> id >> t;
            dist_change(id, t);
        }
        else if (query == 400)
        {
            print_ans();
        }
    }
}