| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 167 | 28 | 22 | 26.829% |
문제
생물학자를 꿈꾸는 강산이는 새해 선물로 현미경을 받았다.
어느 날, 물 속에 있는 박테리아의 움직임을 관찰하고 있었다. 관찰을 한 시간 정도 하다보니, 일정한 규칙대로 움직인다는 것을 알 수 있었다.
물방울은 크기가 무한대인 정사각형 격자로 모델링 할 수 있다. 박테리아는 한 정사각형에 있다. 박테리아가 움직이는 방향은 다음과 같이 숫자로 표현할 수 있다.
모든 박테리아는 동시에 움직이고, 1초 단위로 움직이고, 한 방향으로만 움직인다. 박테리아 여러 마리가 같은 칸에 있을 수도 있다.
박테리아의 위치와 움직이는 방향이 주어졌을 때, 박테리아 여러 마리가 같은 칸에 제일 많이 있을 때가 언제인지, 그리고 그 때 몇 마리가 같은 칸에 있었는지 구하는 프로그램을 작성하시오. 만약 이러한 최댓값이 여러개라면, 가장 빠른 시간을 출력한다.
입력
첫째 줄에 박테리아의 수 N(1 ≤ N ≤ 5,000)이 주어진다.다음 N개의 줄에는 세 개의 정수 X, Y, D (-1,000,000 ≤ X,Y ≤ 1,000,000), (1 ≤ D ≤ 8) 가 주어진다.
X와 Y는 박테리아의 시작 좌표이며, D는 방향이다. X값은 왼쪽에서 오른쪽으로 갈 수록 증가하며, Y값은 위로 갈수록 증가한다.
박테리아의 시작 위치가 겹치는 경우는 없으며, 적어도 한 번은 박테리아가 만난다.
출력
첫째 줄에 박테리아가 같은 칸에 가장 많이 있었을 때, 몇 마리나 있었는지 출력한다. 둘째 줄에는 그 때의 시간을 출력한다.
접근
좌표의 범위가 크기 때문에, 좌표로 데이터를 저장하면 안된다.
그래서 시간으로 테이블을 만들고, 동시간대에 만나는 박테리아들을 저장한다.
2중 loop를 만들어서 각각 몇초에 만나는지 저장을 하면 된다.
i가 1중이고, j가 2중이라고 가정하면
i에 들어갔을때, i + 1 ~ N 까지 j가 순회한다.
이 때, 만나는 시간을 추가하는데 여기에 구현 기법이 필요하다.
이는 하단 풀이에서 서술한다.
두 박테리아가 만나는 것은 연립방정식을 통해 해결할 수 있다.
각 박테리아를 A, B라고 가정하면, x에서 만나는 경우는 크게 두가지다.
A.x와 B.x가 같고, A.dx와 B.dx도 같아야 한다.
이 경우에는 y가 언제 만나는지 찾아서 t에 넣어주면 된다.
물론 만나지 못하는 경우도 고려해야 된다.
A.x와 B.x가 다른 경우는
A.x + A.dx * t = B.x + B.dx * t
이 방정식을 통해 t를 구할 수 있다.
이 후 y의 식에도 넣어보고, 같은 좌표인지 확인한다.
풀이
각 i가 순회할 때 마다, 시간의 임시 테이블 tmp를 이용한다.
처음 tmp[t]에 가는 경우는, i와 다르므로 table에 2를 넣는다. (박테리아 2개)
tmp[t] == i인 경우는 해당 인덱스이므로 + 1을 해준다. (새로운 박테리아 추가)
#include <bits/stdc++.h>
using namespace std;
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define CIN(a) cin >> a;
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define ENDL cout << '\n'
int dy[9] = { 0, 1, 1, 1, 0, -1, -1, -1, 0 };
int dx[9] = { 0, -1, 0, 1, 1, 1, 0, -1, -1 };
struct Bug
{
int x, y, d;
Bug() {}
};
int N, max_num = 0, min_time = 0;
Bug bug[5001];
int table[2000001], tmp[2000001];
void solve(Bug A, Bug B, int idx)
{
int mother, son, t;
if (dx[A.d] == dx[B.d]) // x 움직임이 같은 경우
{
if (A.x != B.x) return; // x 좌표가 다르면 불가능
son = A.y - B.y;
mother = dy[B.d] - dy[A.d];
if (mother == 0) return; // x좌표가 같으므로 y 좌표는 다름
else if (son % mother != 0) return; // 못 만나는 경우
t = son / mother;
}
else // x 움직임이 다른 경우
{
son = A.x - B.x;
mother = dx[B.d] - dx[A.d];
if (son % mother != 0) return;
t = son / mother;
if (A.y + dy[A.d] * t != B.y + dy[B.d] * t) return;
}
if (t < 0) return;
if (tmp[t] != idx)
{
tmp[t] = idx;
table[t] = 2;
}
else table[t]++;
if (table[t] > max_num)
{
max_num = table[t];
min_time = t;
}
else if (table[t] == max_num) min_time = min(min_time, t);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
CIN(N);
FUP(i, 1, N) CIN3(bug[i].x, bug[i].y, bug[i].d);
FUP(i, 1, N - 1)
{
FUP(j, i + 1, N)
{
solve(bug[i], bug[j], i);
}
}
COUT(max_num);
ENDL;
COUT(min_time);
return 0;
}