취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 27475번 문제인 Cancel the Trains이다.
문제는 아래 링크를 확인하자.

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

(i,0)에서 출발하는 열차와 (0,j)에서 출발하는 열차가 공통으로 지나는 점은 (i,j) 하나뿐이다. 즉, 두 열차가 충돌하려면 이 지점에서 충돌해야한다.

각 열차가 단위시간에 1만큼 이동한다고 가정할 때(열차의 속도는 일정하므로), 각 열차는 i, j의 시간이 지난 시점에 (i,j)를 통과함을 관찰하자. 이 관찰을 통해 두 열차가 충돌한다는 것과 i와 j가 같아야한다는 것은 필요충분조건임을 알 수 있다.

위 내용을 이용해 문제를 해결하자. 즉, 횡방향으로 움직이는 열차의 y좌표와 종방향으로 움직이는 열차의 x좌표 중 값이 겹치는 개수를 세어 문제를 해결하자. 이는 배열을 이용해 간단히 구현할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <cstring>
using namespace std;

int T, N, M;
int arr[101];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> T;

	while (T--) {
		int ans = 0;
		memset(arr, 0, sizeof(arr));
		cin >> N >> M;
		while (N--) {
			int x; cin >> x;
			arr[x]++;
		}
		while (M--) {
			int x; cin >> x;
			if (arr[x]) ans++;
		}

		cout << ans << '\n';
	}
}