이번 문제는 백준의 실버 1 문제인 개미 문제이다.
문제를 차근 차근 한번 읽어보자.
먼저 개미가 올라갈 최대 100만 길이의 막대가 주어진다.
개미는 최대 10만 마리까지 주어지며, 개미의 위치가 주어진다.
개미가 모두 떨어질 수 있는 최소 및 최대 시간을 구해달라고 한다.
직관적인 생각
먼저 직관적으로 한 번 생각해보자.
언제 최소 시간이고 언제 최대 시간이 될 수 있을까?
최소 시간은 매우 간단하다.
모든 개미가 아무 개미와도 부딪히지 않는다면, 최소 시간일 것이다.
가운데에 가장 가까운 개미가 아무와도 부딪히지 않고 떨어질 수 있을 때,
즉 가운데를 기준으로 개미가 대칭으로 움직여 아무도 부딪히지 않을 때
최소 시간이 보장된다고 생각한다.
하지만 관건은 최대 시간일 때를 계산하는 것이다.
최대 시간일 때는 단순히 가운데의 개미 둘이 부딪혔을 때일까?
그렇게 단순히 계산이 가능한 문제가 아니다.
다른 개미들이 반대로 움직였을 때, 튕기는 경우도 생각을 해야 한다.
그 말은 가운데를 기준으로 모든 개미가 마주보고 걸어온다는 말이다.
그럼 가장 가운데의 개미 둘은 계속해서 튕기게 될 것이다.
이 경우가 분명히 최대 시간이 되는 경우임은 확실하다.
하지만 어떻게 시간 계산을 구현할 수 있을까?
단순하게 생각하기
도저히 생각이 안나, 결국 다른 사람의 풀이를 참고했다.
사실 이 문제는 딱히 구현이 필요한 문제가 아니었다.
내가 너무 복잡하게 생각한 것이다.
개미가 서로 부딪히는 시점을 우리는 고려할 필요가 없다.
왜냐하면 지나는 두 개미를 우리는 구분할 수 없기 때문이다!
두 개미가 부딪히더라도, 자기 갈 길을 간다고 봐도 동일하다.
그 말인 즉, 우리가 구해야 할 최소 최대 시간은 아래와 같다.
- 빨리 떨어질 수 있는 위치 중 최대가 최소 시간!
- 늦게 떨어질 수 있는 위치 중 최대가 최대 시간!
구현
우선 간단하게 아래와 같이 구현하였다.
int main() {
optimize();
cin >> tc;
while (tc--) {
int stick_len = 0, num = 0, pos = 0, min_time = 0, max_time = 0;
cin >> stick_len >> num;
for (int i = 0; i < num; i++) {
cin >> pos;
int temp_min = min(pos, stick_len - pos);
int temp_max = max(pos, stick_len - pos);
min_time = max(temp_min, min_time);
max_time = max(temp_max, max_time);
}
cout << min_time << " " << max_time << '\n';
}
return 0;
}문제에 조금 더 단순하게 접근하려는 사고가 필요할 것 같다.