사용한 알고리즘
알고리즘 설명
- 아래서 부터 하나씩 막대기를 올라가는 시뮬레이션을 진행한다.
- 막대기가 올라갈 수 있으려면 서로 곂쳐야만 올라 갈 수 있다.
- 이를 위해서 막대기가 시간 t일 경우 어느 좌표에 있는지를 계산하고 서로 좌표를 이용하여 겹치는지를 확인한다.
- 좌표가 겹친다면 다음 막대기로 옮기고, 이를 겹치지 않을때까지 반복한다.
- 좌표가 겹치지 않는다면, 좌표가 곂치기까지 시간을 계산하여 시간을 추가한다.
- 위를 마지막 막대기에 도착할때까지 반복한다.
풀이
// baekjoon 2528 yechan
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N=3001;
int N, L, t;
pair<int, int> stick[MAX_N];
// 막대기에 왼쪽 좌표 출력
inline int getFst(int a, int t) {
if (L-stick[a].first == 0) return 0;
return (stick[a].second + t/(L-stick[a].first))%2 ? (L-stick[a].first-t%(L-stick[a].first)) : t%(L-stick[a].first);
}
// 막대기에 오른쪽 좌표 출력
inline int getScd(int a, int t) {
if (L-stick[a].first == 0) return L;
// 막대기가 움직이는 방향이 왼쪽인지, 오른쪽인지
return (stick[a].second + t/(L-stick[a].first))%2 ? (L-t%(L-stick[a].first)) : t%(L-stick[a].first)+stick[a].first;
}
// 둘간에 간격 중 작은 부분을 출력
// 두 막대기가 서로 겹치지 않았다면, (a1,a2)와 (b1,b2)에서 간격은 아래와 같은 2가지 조건으로 나눠진다.
// Always: a1 < a2, b1 < b2, no overlap
// case1. a2 < b1 인 경우, gap = b1 - a2
// case2. b2 < a1 인 경우, gap = a1 - b2
inline int gap(int a, int b, int t) {
return min(abs(getFst(a, t)-getScd(b, t)), abs(getFst(b, t)-getScd(a, t)));
}
// 시간이 t 일때 a번째 막대기와 b번째 막대기가 서로 겹쳐지는지
bool isOverlap(int a, int b, int t) {
if (getScd(a, t) < getFst(b, t)) return false;
if (getScd(b, t) < getFst(a, t)) return false;
return true;
}
int main() {
scanf("%d%d", &N, &L);
for (int i=0; i<N; i++)
scanf("%d%d", &stick[i].first, &stick[i].second);
int i=0; // curFloor
while (i < N - 1) {
// 막대기가 i번째와 i+1번째가 서로 곂치는지 확인
while (i < N-1 && isOverlap(i, i+1, t)) i++;
if (i == N-1) break;
// 막대기 간에 차이를 구하고 시간을 증가시킴
t += (gap(i, i+1, t)+1)/2;
}
printf("%d\n", t);
return 0;
}
