Baekjoon 3221번 개미의 이동

문제

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

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

bool compare(int a, int b){
    return a < b;
}

int main(){
    fastio;
    int L, T;
    cin >> L >> T;
    int N;
    cin >> N;
    int l;
    char d;
    vector<int> ans;
    for(int i = 0; i < N; i++){
        cin >> l >> d;
        if(d == 'L'){
            if(T > l){ // R
                int time = T-l;
                int half = time/L;
                int remain = time-L*half;
                if(half%2 == 0){ // R
                    ans.push_back(remain);
                }
                else{ // L
                    ans.push_back(L-remain);
                }
            }
            else{ // L
                ans.push_back(l-T);
            }
        }
        else{
            if(T > L-l){ // L
                int time = T-(L-l);
                int half = time/L;
                int remain = time-L*half;
                if(half%2 == 0){ // L
                    ans.push_back(L-remain);
                }
                else{ // R
                    ans.push_back(remain);
                }
            }
            else{ // R
                ans.push_back(l+T);
            }
        }
    }
    sort(all(ans), compare);
    for(int i : ans) cout << i << " ";
    cout << "\n";
    return 0;
}

문제에서 개미는 장애물(다른 개미나 줄의 끝)을 마주치면 방향을 바꾼다고 한다. 다시말해 모든 개미는 일정한 범위 내에서 좌우로 움직이는 것을 반복한다. 여기서 왼쪽에서부터 차례대로 입력받은 개미의 순서는 시간이 지나도 바뀌지 않는다는 것을 알 수 있다.

개미의 순서가 바뀌지 않는다는 사실도 매우 중요하지만 이것만으로는 시간안에 문제를 해결할 수 없다.

예제를 여러개 더 손으로 풀다보면 개미는 장애물을 마주치면 방향을 바꾸지만, 실제로는 스쳐 지나가는 것과 다를 게 없다는 사실을 알 수 있다. 즉, 모든 개미들이 다른 개미를 신경쓰지 않고 오직 줄의 끝에서만 방향을 바꾸며 T 초동안 이동시킨 후 정렬한 것이 정답이 된다.