14930 구슬 (BEAD)

으악! 개미문제! 어렵다. 아이디어는 알겠는데 약간 마음으로 이해가 안 된다. 둘이 부딪쳤는데 위치는 같다.. 🧐

 

하나하나 생각해보면 어떻게 돌아가는지 알겠다. 구슬이 부딪쳐도 속도는 같아서 구슬 하나가 움직인 것과 같다. 

 

이럼 또 아니 근데 실제로는 안 움직이잖아요,,, 생각이 드는데 이걸 또 하나하나 움직임을 생각해보면 구슬 하나가 자기 경로로 계속 움직인다는 걸 알게 된다. 

 

그래서 이 문제에 쓰인 아이디어

- 속도는 유지된다

- 구슬 하나가 x + v * t만큼 움직인 위치는 그대로이다

- 구슬의 순서는 유지된다 (부딪혀서 위치가 바뀌지 않으므로)

 

빨간 구슬이 k번째에 있다고 가정했을 때, 

위치를 전부 x + v * t 기준으로 정렬하고 k번째 위치가 빨간 구슬의 위치이다. 

 

아이디어 너무 재밌다. 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>
#include <sstream>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int main() {
    i64 n, t;
    scanf("%lld %lld", &n, &t);
    
    vector<ii64> v(n);
    for (int i = 0; i < n; i++) {
        scanf("%lld %lld", &v[i].xx, &v[i].yy);
    }
    
    // 빨간 구슬의 순번 k를 구함
    i64 redX = v[0].xx;
    i64 k;
    sort(all(v));
    for (int i = 0; i < n; i++) {
        if (v[i].xx == redX)
            k = i;
    }
    
    // x + v * t 기준으로 정렬
    for (int i = 0; i < n; i++) {
        v[i].xx = v[i].xx + v[i].yy * t;
    }
    
    sort(all(v));
    
    
    // k번째를 구함
    printf("%lld", v[k].xx);
    
    return 0;
}