[BOJ] 4307번_개미_애드 혹 (C++)

[문제]

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

1cm/s로 움직이는 개미 n마리가 lcm 길이의 막대 위에 존재한다. 이때 개미는 막대 끝까지 걸어가면 떨어지며, 두 개미가 만나면 방향을 반대로 바꾸어 걸어가게 된다.
가장 처음에 개미 n마리가 존재하는 위치를 알고 있지만, 개미가 어느 방향으로 움직이는 지 알 수 없을 때 모든 개미가 떨어질 때까지 걸리는 시간의 최소값과 최대값을 구하는 문제이다.

• 이 문제는 정답률이 무려 49%이상으로 매우 높은 편인데, 나한테는 너무 어렵게 느껴졌고 스스로의 힘으로 풀지 못하였다. 나는 애드 혹 문제를 이 문제를 통해 처음 접해봤다. 구글검색을 통해 애드 혹 문제는 아이디어가 정말 중요하다는 것을 깨달았다.

[사용 알고리즘]

애드 혹

• 애드 혹이란?
  프로그래밍에서 애드 혹이란 해당 문제를 해결하는데 정형화된 알고리즘을 쓰지 않고 해결할 수 있는 유형의 문제를 말한다.

[풀이 핵심]

• 해당 문제가 어렵게 느껴지는 이유는 "두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다." 라는 조건 때문인데, 깊게 생각해보면 두 개미가 만나게 되어 방향을 바꿔 이동하지만, 두 개미를 식별할 방법이 없다고 생각해보면 방향을 바꾸지 않고 앞으로 가는 것처럼 보이며, 똑같은 방향으로 계속 가는 것과 다를 것이 없다는 것이다.
• 따라서 최소값은 개미의 현재 위치에서 부터 막대의 가장 가까운 끝까지 이동하는데 걸리는 시간 중 가장 오래걸리는 개미의 이동 시간이며, 최대값은 개미의 현재 위치에서 부터 막대의 가장 먼 끝까지 이동하는데 걸리는 시간 중 가장 오래걸리는 개미의 이동 시간이다.

[코드]

//boj4307번_개미_애드 혹

#include<iostream>
#include<vector>

using namespace std;

int main() {
	int T;
	cin >> T;

	for (int t = 0; t < T; t++) {
		int l, n;
		cin >> l >> n;

		vector<int> v;

		for (int i = 0; i < n; i++) {
			int ant;
			cin >> ant;
			v.push_back(ant);
		}

		int Time_max = 0;
		int Time_min = 0;

		for (int i = 0; i < v.size(); i++) {
			int dis_long = max(v[i], l - v[i]);
			int dis_short = min(v[i], l - v[i]);

			Time_max = max(Time_max, dis_long);
			Time_min = max(Time_min, dis_short);
		}

		cout << Time_min << " " << Time_max << '\n';
	}

	return 0;
}