[백준 14930번] 구슬 (BEAD) 풀이

#백준 #백준 14930번 #백준 구슬 (BEAD)

 

14930번: 구슬 (BEAD)

이 문제는 백준 4307번 개미와 유형이 비슷한 문제로, 수직선 위에서 개미나 구슬 등의 물체들이 충돌할 때 결과를 구하는 문제이다. 이러한 유형의 문제를 해결하기 위해서는 두 가지 사실을 알아야 한다.

1) t초 후 구슬들의 순서는 변하지 않는다.

2) 완전탄성충돌한 두 구슬은 속도가 교환된다.

 

첫번째 전제 부터 살펴보면,

 

구슬들의 초기 위치

 

초기 위치가 3인 구슬은 초기 위치가 -2인 구슬과 초기 위치가 4인 구슬 사이에서 움직인다. 구슬은 좌우에 있는 구슬과만 충돌할 수 있으며 그 사이를 움직이게 된다. 따라서 t초가 지나더라도 구슬들의 순서는 처음 상태와 동일하다. 빨간 구슬이 t초 움직였을 때, 수직선 상의 위치는 달라지지만 전체 구슬 중 순서는 처음 순서인 3번째와 동일하게 유지된다.

 

두번째로, 완전탄성충돌한 두 구슬은 속도가 교환되어 처음 속도와 동일하게 움직인 것으로 간주된다. 속도가 3인 구슬과 속도가 -4인 구슬이 서로를 향해 움직이고 있다고 가정해보자. 두 구슬은 충돌하게 된다.

 

서로를 향해 움직이다 충돌한 두 구슬

 

완전탄성충돌한 두 구슬은 속도가 교환된다.

 

속도가 교환된 두 구슬

 

이 때, 두 구슬의 색깔을 바꾸어 생각해보자. 충돌 전 그림과 비교하였을 때, 충돌 결과는 회색 구슬과 빨간색 구슬이 각각 처음 방향과 속도 그대로 움직인 결과와 같다. 즉, t초 동안 이동한 결과의 형태는 구슬들이 처음 속도 그대로 t초 동안 움직인 결과와 같다.

 

두 구슬의 색을 바꾸었을 때

 

위의 두가지 전제를 결합해보자.
구슬들이 t초 동안 이동, 충돌한 결과는 각 구슬들이 초기 속도 그대로  t초 동안 움직였을 때의 구슬 배치와 같다. 따라서 각 구슬들의 나중 위치(현재 위치 + 초기 속도 * t) 를 구하여 벡터에 저장하고 이를 순서대로 정렬한다.

 

vector<long long> vPos(N);
for (int i=0; i<N; i++)
    vPos[i] = v[i].pos+v[i].vel*T;
sort(vPos.begin(), vPos.end());

이동 전 빨간 구슬의 순서를 idx에 저장해 놓았을 때, t초 후 빨간 구슬의 순서는 동일하게 idx가 된다. 따라서 구슬들의 t초 후 좌표에서 idx번째 위치를 가져온다.

 

printf("%lld", vPos[idx]);

문제 해결의 전체 코드는 다음과 같다.

 

#include <iostream>
#include <cstdio>
#include <algorithm> 
#include <cstring>
#include <vector>
#include <cmath>
#include <tuple>
using namespace std;
using ll = pair<long long, long long>;

#define pos first
#define vel second

int main() {

    int N, T;
    scanf("%d %d", &N, &T);

    vector<ll> v(N);
    for (int i=0; i<N; i++)
        scanf("%lld %lld", &v[i].pos, &v[i].vel);
    
    ll red = v[0];
    sort(v.begin(), v.end());
    int idx = find(v.begin(), v.end(), red)-v.begin();

    vector<long long> vPos(N);
    for (int i=0; i<N; i++)
        vPos[i] = v[i].pos+v[i].vel*T;
    sort(vPos.begin(), vPos.end());

    printf("%lld", vPos[idx]);
    return 0;
}