PS/SCPC

[SCPC - 2018년 1차 예선] 버스 타기 (JAVA)

제이온 (Jayon) 2020. 8. 19.

문제

N명의 바둑 선수들이 몇 대의 버스에 나누어 타려고 한다.
선수들은 1부터 N까지 번호가 붙어 있다. 각 선수는 실력 값을 가지고 있다.
선수 i번의 실력 값을 Ai라고 하자.



선수들 간의 경쟁심 때문에 두 선수의 실력 차이가 KK이하인 경우는 같은 버스에 타지 않는다고 한다.
즉, 두 선수 i번과 j번의 (ij) 실력이 |AiAj| K|Ai−Aj| ≤ K를 만족하는 경우 같은 버스에 타지 않는 것이다. 
한 대의 버스에 탈 수 있는 인원은 무제한이라고 한다. 



철수는 선수들의 실력을 입력으로 받아서 필요한 버스 수의 최소값을 계산하려고 한다.
여러 선수들이 서로 같은 버스를 타지 않는 관계가 매우 복잡해 보이지만, 철수는 아주 간단한 계산 방법이 있다는 것을 알게 되었다.
철수를 도와서 버스 수의 최소값을 계산하는 프로그램을 작성하라.

 

 

입력

입력 파일에는 여러 테스트 케이스가 포함될 수 있다. 파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T 가 주어지고, 이후 차례로 T 개의 테스트 케이스가 주어진다. (1≤T≤50) 각 테스트 케이스의 첫 줄에 선수의 인원 수 N(1≤N≤200,000)과 실력 범위 K(1≤K≤1,000,000,000)가 주어진다. 다음 줄에 각 선수의 실력 값이 자연수로 주어진다. 선수들의 실력 값은 1 이상 1,000,000,000 이하의 자연수이며 모두 다르다.

 

 

출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,
각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 C는 테스트 케이스의 번호이다.
그 다음 줄에 최소의 버스 대수를 계산하여 출력한다.

 

 

풀이

그리디 알고리즘을 사용하여 풀 수 있는 문제였습니다.

 

전반적인 로직은 아래와 같습니다.

 

 

1. i번째 선수와 j번째 선수가 같은 버스를 탈 수 없는 경우

 

1-1. ans를 1 증가시키고, 다음 과정에서는 i번째 선수와 (j + 1)번째 선수를 비교한다.

(ans는 1부터 시작한다고 가정.)

 

2. i번쨰 선수와 j번쨰 선수가 같은 버스를 탈 수 없는 경우

 

2-1. ans를 그대로 두고, 다음 과정에서는 (i + 1)번째 선수와 (j + 1)번째 선수를 비교한다.

 

 

예시를 하나 들어서 설명해 보겠습니다.

 

N = 5, K = 2

arr = {1, 3, 4, 7, 8}

 

ans = 1부터 시작.

처음에는 arr[0]과 arr[1]을 비교합니다. arr[1] - arr[0] = 2로, K보다 작거나 같으므로 같은 버스를 탈 수 없습니다.

따라서, ans를 1 증가시키고, 다음에는 arr[2]와 arr[0]을 비교합니다.

arr[2] - arr[0] = 3으로, K보다 큽니다. 따라서 같은 버스를 탈 수 있으므로 ans를 그대로 두고, 다음에는 arr[3]과 arr[1]을 비교합니다.

 

이와 같은 과정을 반복하면, {1, 4, 8}, {3, 7}로 묶여서 2개의 버스가 필요하다는 것을 알 수 있습니다.

또한 이를 식으로 표현하면, arr[i] - arr[i - ans] (i는 1부터 시작) 이라 할 수 있습니다.

 

아래는 위 풀이를 정리한 소스코드입니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.

댓글

추천 글