[BOJ] 3163_떨어지는 개미

떨어지는 개미

문제 링크: https://www.acmicpc.net/problem/3163

3163번: 떨어지는 개미

2차 시도 (성공)

https://www.acmicpc.net/board/view/28512
여기서 도움을 받았다.

처음에 충돌 횟수와 해당 거리를 모두 구해서 각 개미의 멤버 변수에 저장하려 했다.
위 도움을 받고 충돌횟수는 중요한 것이 아님을 깨달았다.

 

 

 

위 이미지와 같을 때 왼쪽으로 떨어지는 친구들은 1과 2, 오른쪽으로 떨어지는 친구는 3이다.
그렇다면 1이 떨어지는 때는 언제인가? 12의 위치에서 2와 충돌 후 방향을 바꾸고 왼쪽에서 떨어질 것이다.
시간은 7 + 1 + 12 = 20이다.
2가 떨어지는 때는? 13의 위치에서 1과 충돌 후 방향을 바꾸고 다시 14의 위치에서 3과 충돌 후 왼쪽에서 떨어질 것이다.
시간은 7 + 1 + 1 + 1 + 14 = 24이다.
3은 15의 위치에서 2와 충돌 후 오른쪽에서 떨어질 것이다. 시간은 9 + 1 + 15 = 25

만일 충돌 없이 떨어지는 시간을 구하면 각각 25, 20 24의 시간이 걸릴 것이다. 또한 방향이 왼쪽으로 2개 오른쪽으로 1개가 떨어진다. 위의 경우랑 비교해보자.

시간과 왼쪽 및 오른쪽으로 떨어지는 수가 일치한다.

---

모두가 같은 속도로 움직이기 때문에 모든 개미는 일정 거리 이동 후 결국 막대 위에서 떨어질 수 밖에 없다.

임의로 고른 개미를 기준으로 그 개미보다 안에 있는 하나의 개미는 항상 고른 개미가 충돌 없이 지나갈 때의 거리를 움직이게 된다.
위 예시처럼 2보다 안에 있는 개미는 1이므로 1은 20의 거리만큼 이동하게 되고, 3보다 안에 있는 개미는 2와 1인데, 1은 정해져 있으므로 2의 거리가 24만큼을 이동하게 된다.

따라서, 왼쪽으로 떨어질 개미들과 오른쪽으로 떨어질 개미들을 구분 지어서 충돌 없는 경우의 거리를 모두 구해주고, 이와는 별개로 전체 개미의 index를 고정해주어 왼쪽부터 충돌 없는 경우의 거리와 매칭해준다.

• 정답 코드

    #include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
  
    class ants {
    private:
        int id;
        int cur;
        int direction;
        int time;
    public:
        ants(int p, int a, int l) {
            if (a < 0) {
                this->direction = -1;
                this->time = p;
            }
            else {
                this->direction = 1;
                this->time = l - p;
            }
            this->id = a;
            this->cur = p;
        }
  
        int getCur() {
            return this->cur;
        }
        int getID() {
            return this->id;
        }
        int getTime() {
            return this->time;
        }
        void setTime(int time_) {
            this->time = time_;
        }
        int getDirection() {
            return this->direction;
        }
    };
  
    bool compare(ants* rhs1, ants* rhs2) {
        return rhs1->getCur() < rhs2->getCur();
    }
    bool compareLeft(ants* rhs1, ants* rhs2) {
        return rhs1->getTime() < rhs2->getTime();
    }
    bool compareRight(ants* rhs1, ants* rhs2) {
        return rhs1->getTime() > rhs2->getTime();
    }
  
    bool compare3(ants* rhs1, ants* rhs2) {
        if (rhs1->getTime() == rhs2->getTime())
            return rhs1->getID() < rhs2->getID();
  
        return rhs1->getTime() < rhs2->getTime();
    }
  
    int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL); cout.tie(NULL);
        int T;
        cin >> T;
        while (T--) {
            int n, l, k, left = 0, right = 0;
            cin >> n >> l >> k;
            vector<ants*> antList;
            vector<ants*> LeftDirection;
            vector<ants*> RightDirection;
            while (n--) {
                int p, a;
                cin >> p >> a;
                if (a < 0) {
                    left++;
                    LeftDirection.push_back(new ants(p, a, l));
                }
                else{
                    RightDirection.push_back(new ants(p, a, l));
                }
                (a < 0 ? left++ : right++);
                antList.push_back(new ants(p, a, l));
            }
  
            sort(antList.begin(), antList.end(), compare); //index 별로 정렬
            sort(LeftDirection.begin(), LeftDirection.end(), compareLeft); //왼쪽 방향의 데이터들을 시간 순으로 정렬
            sort(RightDirection.begin(), RightDirection.end(), compareRight); //오른쪽 방향의 데이터들을 시간 순으로 정렬
  
            for (int i = 0; i < LeftDirection.size(); i++)
                antList[i]->setTime(LeftDirection[i]->getTime());
            int index = LeftDirection.size();
            for (int i = index; i < antList.size(); i++)
                antList[i]->setTime(RightDirection[i - index]->getTime());
  
            sort(antList.begin(), antList.end(), compare3); //시간순으로 정렬
  
            cout << antList[k - 1]->getID() << "\n";
        }
        return 0;
    }

1차 시도 (실패)

개미들을 하나의 객체로 생성한다.
객체는 id와 현재 위치, 방향, 다음 이동할 위치를 가지고 있다.
1초가 지나면서 각 개미가 방향을 가지고 움직이기 전에 다음 움직일 위치가 다른 객체와 부딪힐 경우를 체크한다.
부딪힐 경우 방향을 바꾸고 다음의 위치 또한 방향을 바꾼 값으로 지정한다.
방향을 바꾼 후 모두 한 칸씩 이동한다.

이동 후 막대에서 떨어진 경우 즉, 현재 위치가 0보다 작거나 30보다 큰 경우를 체크하고 떨어진 리스트에 저장한다.
떨어진 리스트에 저장하는데, 동시에 떨어진 경우 ID를 비교하여 더 작은 경우를 우선적으로 넣어준다.
그리고 k번째로 떨어진 개미의 ID를 출력한다.
index로는 dropList[k-1]에 위치한다.

 

• 미해결 코드

    #include<iostream>
    #include<deque>
    #include<algorithm>
    using namespace std;
  
    class ants {
    private:
        int id;
        int cur;
        int next;
        int direction;
    public:
        ants(int p, int a) {
            this->direction = (a < 0 ? -1 : 1);
            this->id = a;
            this->cur = p;
            this->next = p + direction;
        }
        void flip() {
            this->direction *= -1;
            this->next = cur + direction;
        }
        void move() {
            this->cur = this->next;
            this->next += direction;
        }
        int getNext() {
            return this->next;
        }
        int getCur() {
            return this->cur;
        }
        int getID() {
            return this->id;
        }
        bool operator<(const ants& rhs) const {
            return this->cur < rhs.cur;
        }
    };
  
    bool compare(ants* rhs1, ants* rhs2) {
        return rhs1->getCur() < rhs2->getCur();
    }
  
    bool isTurn(ants* rhs1, ants* rhs2) {
        if (rhs1->getNext() < rhs2->getNext()) {
            return false;
        }
  
        return true;
    }
  
    int main() {
        int T;
        cin >> T;
        while (T--){
            int n, l, k;
            cin >> n >> l >> k;
            deque<ants*> antList;
            deque<ants*> dropList;
            while (n--) {
                int p, a;
                cin >> p >> a;
                //ants* temp = new ants(p, a);
                antList.push_back(new ants(p, a));
            }
  
            sort(antList.begin(), antList.end(), compare);
  
            for (auto iter = antList.begin(); iter != antList.end(); ++iter)
                cout<< (*iter)->getCur()<< ' ';
            cout << endl;
  
            while (!antList.empty()) {
                bool front = false, back = false;
                // 다음 행진에서 방향 바꿀거 있으면 바꿈
                for (int i = 0; i < antList.size() - 1;i++) 
                    if (isTurn(antList[i], antList[i + 1])) {
                        antList[i]->flip();
                        antList[i + 1]->flip();
                    }
                // 모두 행진
                for (auto iter = antList.begin(); iter != antList.end(); ++iter) 
                    (*iter)->move();
  
                if (antList.front()->getCur() < 0)
                    front = true;
                if (antList.back()->getCur() > l)
                    back = true;
  
                if (front && back) {
                    if (antList.front()->getID() < antList.back()->getID()) {
                        dropList.push_back(antList.front());
                        dropList.push_back(antList.back());
                    }
                    else {
                        dropList.push_back(antList.back());
                        dropList.push_back(antList.front());
                    }
                    antList.pop_front();
                    antList.pop_back();
                }
                else if (front) {
                    dropList.push_back(antList.front());
                    antList.pop_front();
                }
                else if (back) {
                    dropList.push_back(antList.back());
                    antList.pop_back();
                }
            }
  
            cout << dropList[k-1]->getID() << "\n";
        }
        return 0;
    }