문제 설명
n명의 사람이 있고, 동일한 투표 기계가 두 대 있다고 가정해 보겠습니다. 또한 크기가 n인 배열 time이 주어지며, time[i]는 i번째 사람이 어느 한 기계에서 투표를 완료하는 데 걸리는 총 시간을 나타냅니다. 같은 시점에는 각 기계마다 한 명씩만 사용할 수 있습니다. 그리고 기계가 가동될 수 있는 최대 허용 시간을 나타내는 값 x가 주어질 때, 모든 사람이 이 제한 시간 안에 투표를 마칠 수 있는지 판별해야 합니다.
예를 들어 입력이 n = 3, x = 7, time = [3, 5, 3]이라면 결과는 True입니다. 시각 t0에 0번째 사람은 첫 번째 기계로, 1번째 사람은 두 번째 기계로 이동합니다. 시각 t3에 첫 번째 기계가 비워지면 2번째 사람이 첫 번째 기계로 이동하고, 시각 t5에 두 번째 기계가, 시각 t6에 첫 번째 기계가 차례로 비게 되므로 모든 참가자가 제한 시간 내에 투표를 마친 것입니다.
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- time 배열의 모든 요소의 합을 total_sum에 저장합니다.
- total_sum <= x라면 True를 반환합니다.
- time 리스트를 오름차순으로 정렬합니다.
- time과 같은 크기의 배열 prev_sum을 만들고 0으로 초기화합니다.
- prev_sum[0] := time[0]으로 설정합니다.
- i를 1부터 prev_sum의 크기까지 반복하며 prev_sum[i] := prev_sum[i - 1] + time[i]로 누적 합을 계산합니다.
- i를 0부터 prev_sum의 크기까지 반복하면서,
- j를 i + 1부터 prev_sum의 크기 - 1까지 반복하며 다음을 수행합니다.
- temp_sum := prev_sum[i] + (total_sum - prev_sum[j])를 계산합니다.
- temp_sum <= x이고 total_sum - temp_sum <= x라면 True를 반환합니다.
- j를 i + 1부터 prev_sum의 크기 - 1까지 반복하며 다음을 수행합니다.
- 모든 조건을 만족하지 못하면 False를 반환합니다.
핵심 아이디어는 사람들을 세 그룹으로 나누어, 각 그룹의 총 투표 시간이 모두 x 이하가 되도록 배분할 수 있는지 검사하는 것입니다. 누적 합 배열을 활용하면 각 분할 지점에서의 그룹 합을 효율적으로 계산할 수 있습니다.
구현 예제
def solve(n, x, time): total_sum = sum(time) if total_sum <= x: return True time.sort() prev_sum = [0 for i in range(len(time))] prev_sum[0] = time[0] for i in range(1, len(prev_sum)): prev_sum[i] = prev_sum[i - 1] + time[i] for i in range(0, len(prev_sum)): for j in range(i + 1, len(prev_sum)): temp_sum = (prev_sum[i] + (total_sum - prev_sum[j])) if temp_sum <= x and total_sum - temp_sum <= x: return True return False n = 3 x = 7 time = [3, 5, 3] print(solve(n, x, time))
입력
3, 7, [3, 5, 3]
출력
True