[BOJ/Gold 2] 백준 2136 개미(C++)

문제 링크

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

2136번: 개미

문제

길이가 L(2 ≤ L ≤ 1,000,000,000)인 막대기 위에 N(1 ≤ N ≤ 100,000)마리의 개미들이 서로 다른 위치에 살고 있다. 개미들은 크기가 매우 작기 때문에 이 문제에서는 개미가 크기가 없는 점이라고 생각하자. 각각의 개미의 위치는 x좌표로 표시되며, 좌표값은 0보다 크고 L보다 작은 값으로 표현된다.

각각의 개미는 왼쪽, 혹은 오른쪽으로 움직이고 있다. 모든 개미들은 똑같은 속도로, 1초에 한 칸씩 움직인다. 개미들이 움직이는 도중에 서로 부딪히는 경우가 생길 수도 있다. 두 마리의 개미가 서로 부딪혔을 때, 두 마리의 개미는 모두 즉시 방향을 바꾸어 다시 움직이게 된다.

개미들이 이동하다가 0인 위치나 L인 위치에 도달하게 되면, 그 개미는 막대기 아래로 떨어지게 된다. 개미들의 초기상태가 주어졌을 때, 가장 마지막에 떨어지는 개미와 그 개미가 떨어지는 시각을 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 N, L이 주어진다. 다음 N개의 줄에는 각 개미의 초기 위치가 주어진다. 초기 위치가 양수로 주어지는 경우는 그 값이 그 개미의 위치가 되며, 그 개미는 오른쪽으로 움직이고 있다. 초기 위치가 음수로 주어지는 경우에는 그 절댓값이 그 개미의 위치가 되며, 그 개미는 왼쪽으로 움직이고 있다. 예를 들어 3이 주어지는 경우에는 3인 위치에서 오른쪽으로 움직이고 있고, -7인 경우에는 7인 위치에서 왼쪽으로 움직이고 있다.

출력

첫째 줄에 두 정수 i, t를 출력한다. i는 가장 마지막에 떨어지는 개미의 번호이다. 개미의 번호는 입력에서 주어지는 순서대로 1, 2, …, N이다. t는 가장 마지막에 떨어지는 개미가 바닥에 떨어지는 시간이다. 가장 마지막에 떨어지는 개미가 여러 마리인 경우는 없다고 가정한다.

예제 입력 1

2 5
4
-3

예제 출력 1

2 3

예제 입력 2

1 10
3

예제 출력 2

1 7

알고리즘 분류

• 구현
• 수학
• 정렬
• 애드 혹

풀이

처음에 당연히 구현을 통해서 풀어나가려 했지만 TLE가 떴고, 구글링을 통해서 방법을 알아내었다.

개미가 서로 충돌한다면, 개미의 번호를 모른다고 가정했을 때 그냥 개미들이 충돌하지 않고 서로를 통과해서 제 갈길을 간다고 생각할 수 있다. 

 

코드

#include <iostream>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100005
#define INF 2e9

using namespace std;
int N, L;
int Ant[MAX];
int Left_Ant, Right_Ant;
int Left_Count = 0;
pair<int, int> Ant_Info[MAX];

bool comp(pair<int, int> A, pair<int, int> B) {
	return (A.second < B.second);
}

int main() {
	FIRST
	cin >> N >> L;
	for (int i = 1; i <= N; i++) {
		int X;
		cin >> X;
		Ant[i] = X;
	}
	/*
		개미 A, B가 서로 충돌하면, 개미의 번호를 모른다면 A가 가는 길을 B가 대신 가고,
		B가 가는 길을 A가 대신 간다고 할 수 있다. 따라서, 결론적으로 A와 B가 부딪히든 말든,
		A는 B를 통과해 가던 길을 계속 가고, B도 마찬가지라고 할 수 있다.
		따라서, 오른쪽으로 가는 개미들이 L 지점에서 떨어지는 가장 긴 시간을 구하고,
		왼쪽으로 가는 개미들이 0 지점에서 떨어지는 가장 긴 시간을 구해서
		오른쪽으로 가는 개미가 가장 마지막으로 떨어진다면 왼쪽으로 가는 개미의 수 + 1번째 개미가
		가장 늦게 떨어지는 것이고, 왼쪽으로 가는 개미가 가장 마지막으로 떨어진다면
		왼쪽으로 가는 개미의 수번째 개미가 가장 늦게 떨어지는 것이다.
	*/
	for (int i = 1; i <= N; i++) {
		// 일단 개미의 방향을 파악해서 오른쪽 or 왼쪽으로 가는 개미들이 떨어지는 가장 긴 시간을 구한다.
		if (Ant[i] > 0) {
			Right_Ant = max(L - Ant[i], Right_Ant);
		}
		else if (Ant[i] < 0) {
			Left_Count++;
			Left_Ant = max(abs(Ant[i]), Left_Ant);
		}
		// 그리고 i번째 개미의 번호와 떨어지는 시간을 pair로 묶어 배열에 저장한다.
		Ant_Info[i - 1] = make_pair(i, abs(Ant[i]));
	}
	sort(Ant_Info, Ant_Info + N, comp); // 떨어지는 시간을 기준으로 정렬한다.

	if (Left_Ant < Right_Ant) { // 오른쪽으로 떨어지는 개미들이 떨어지는 데 걸리는 시간이 더 길다면
		cout << Ant_Info[Left_Count].first << " " << Right_Ant << "\n";
		// 떨어지는 시간 순으로 정렬했을 때 왼쪽으로 가는 개미의 수 + 1번째 개미의 번호와 떨어지는 데 걸리는 시간을 출력
	}
	else { // 왼쪽으로 떨어지는 개미들이 떨어지는 데 걸리는 시간이 더 길다면
		cout << Ant_Info[Left_Count - 1].first << " " << Left_Ant << "\n";
		// 떨어지는 시간 순으로 정렬했을 때 왼쪽으로 가는 개미의 수번째 개미의 번호와 떨어지는 데 걸리는 시간을 출력
	}

	return 0;
}