n개의 학생 그룹이 대학 버스를 타고 집에 돌아가기 위해 기다리고 있다고 가정해 보겠습니다. 각 그룹에는 m명의 학생이 있으며, 그룹들은 절대 흩어지지 않고 함께 이동하려고 합니다. 즉, 그룹의 모든 멤버가 버스에 탑승할 수 있을 때만 해당 그룹이 버스에 오를 수 있습니다. 또한 그룹은 반드시 순서대로 탑승해야 하므로, 특정 그룹을 건너뛰고 다음 그룹을 먼저 태울 수는 없습니다.
이때 그룹의 수와 각 그룹의 학생 수가 주어졌다면, 다음 두 조건을 만족하는 버스의 크기를 찾아야 합니다.
- 버스가 모든 그룹을 운송할 수 있어야 한다
- 버스가 대학을 출발할 때마다 차 안에 빈자리가 없어야 한다
예제로 이해하기
입력이 gr_no = [3, 4, 2, 2, 1, 4, 3, 5]라고 해봅시다. 이 경우 출력은 [12, 24]가 됩니다.
- 버스 크기가 12인 경우: 첫 번째 운행에서 1~5번 그룹(3 + 4 + 2 + 2 + 1 = 12명)을 모두 태우고, 두 번째 운행에서 나머지 그룹(4 + 3 + 5 = 12명)을 태울 수 있습니다.
- 버스 크기가 24인 경우: 전체 학생 24명을 한 번의 운행으로 모두 태워 보낼 수 있습니다.
해결 접근 방식
핵심 아이디어는 전체 학생 수의 약수 중에서, 그룹별 누적 인원수가 정확히 버스 크기의 배수 지점과 일치하는 크기를 찾는 것입니다. 단계별로 살펴보면 다음과 같습니다.
- 약수 구하기(factor_ret 함수): 전체 학생 수 n을 입력받아 1부터 √n까지 반복하면서 n을 나누어떨어지게 하는 i와 n/i를 짝지어 목록에 추가한 뒤, 정렬하여 집합 형태로 반환합니다.
- 누적합 계산: total 리스트를 만들어 각 시점까지의 그룹 인원 누적합을 저장합니다. total[i]는 0번부터 i번 그룹까지의 인원 합입니다.
- 버스 크기 검증: 전체 합계의 각 약수(size)에 대해 다음을 확인합니다.
- 누적합 중 size로 나누어떨어지는 값들만 추출합니다.
- 추출된 값들이 size × 1, size × 2, ... 와 순서대로 정확히 일치하는지 검사합니다.
- 모두 일치하면 해당 size를 결과 목록 b_sizes에 추가합니다.
- 검증을 통과한 모든 버스 크기를 담은 b_sizes를 반환합니다.
구현 코드
다음 구현을 통해 더 잘 이해해 보겠습니다.
from functools import reduce
def solve(gr_no):
# 그룹별 누적 인원 계산
total = [gr_no[0]]
for i in range(1, len(gr_no)):
total.append(total[i - 1] + gr_no[i])
b_sizes = []
# 전체 인원의 약수를 후보 버스 크기로 검사
for size in factor_ret(sum(gr_no)):
temp_list = list(filter(lambda x: x % size == 0, total))
index = 1
indicator = True
for point in temp_list:
if point != size * index:
indicator = False
break
index += 1
if indicator:
b_sizes.append(size)
return b_sizes
def factor_ret(n):
# n의 모든 약수를 오름차순으로 반환
return sorted(set(reduce(list.__add__,
([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))
print(solve([3, 4, 2, 2, 1, 4, 3, 5]))입력
[3, 4, 2, 2, 1, 4, 3, 5]
출력
[12, 24]
마무리
이 프로그램은 누적합과 약수 검증만으로 문제를 효율적으로 해결합니다. 약수를 구하는 과정은 O(√N)의 시간 복잡도를 가지며, 각 약수에 대한 검증 역시 누적합 배열을 한 번씩 훑는 수준이므로 실용적인 범위에서 충분히 빠르게 동작합니다. 이처럼 "매 운행마다 빈자리가 없어야 한다는 조건"은 곧 "특정 지점의 누적합이 버스 크기의 배수여야 한다는 조건"으로 바꿔 생각할 수 있다는 점이 이 문제의 핵심입니다.