[백준/BOJ] 4307번 개미 (C/C++)

백준 온라인 저지(BOJ) 4307번 개미

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

4307번: 개미

* 사용언어 : C언어, C++

 

1. 문제

길이가 L 인 막대 위에 N 마리 개미가 있음

개미 1초에 1칸씩 이동하고 막대 마지막에서 떨어짐

만나면 서로 방향을 반대로 바꾸어 이동함

모든 개미가 떨어질 때까지 가장 빠른 시간과 가장 느린 시간 출력

 

2. 풀이

개미의 충돌이 문제의 가장 어려운 부분인데

아이러니하게도 충돌은 아예 무시하고 풀어도 됩니다.

 

왜냐면 충돌 이후 서로 방향을 바꾸는 것과

충돌없이 교차해서 지나가는 것의 결과가 같기 때문입니다.

 

예를 들어 아래 그림 1) 과 같이 충돌하는 상황이 있을 때,

그림 2) 처럼 충돌이 없는 것처럼 처리해도 결과는 똑같습니다.

(각 개미를 구별하여 처리할 필요가 없기 때문)

1) 충돌 고려

2) 충돌 무시

 

충돌을 무시하면 풀이는 단순해집니다.

각 개미 별로 ① 왼쪽으로 떨어지는데 걸리는 시간(pos)과 ② 오른쪽으로 떨어지는데 걸리는 시간(L - pos) 중

큰 값이 가장 오래 걸리는 시간, 작은 값이 가장 적게 걸리는 시간이 됩니다.

 

위에서 구한 값을 전체 탐색하면서 전체의 min, max 와 비교한 뒤 더 큰 값을 저장하고 출력하면 됩니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <stdio.h>

int T, L, N;

int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }

int main() {
	scanf("%d", &T);
	for (int t = 0; t < T; ++t) {
		scanf("%d %d", &L, &N);

		int MIN = 0, MAX = 0;
		for (register int i = 0; i < N; ++i) {
			int pos;
			scanf("%d", &pos);
			
			int shortest = min(pos, L - pos);
			int longest = max(pos, L - pos);

			MIN = max(MIN, shortest);
			MAX = max(MAX, longest);
		}
		printf("%d %d\n", MIN, MAX);
	}
	return 0;
}