C++에서 전체 선분의 중간점이 속한 세그먼트 찾기

이 문제에서는 선분의 길이를 나타내는 크기 m의 배열 arr[]가 주어집니다.

선분은 0부터 arr[0]까지, arr[0]부터 arr[1]까지와 같은 방식으로 순서대로 이어져 있습니다. 우리가 풀어야 할 과제는 전체 선분의 정중앙에 해당하는 중간점이 몇 번째 세그먼트에 속하는지 찾아내는 것입니다.

문제를 쉽게 이해하기 위해 예시를 살펴보겠습니다.

입력

arr[] = {5, 7, 13}

출력

3

설명

세그먼트 : (0, 5), (5, 12), (12, 25)

전체 선분의 총 길이는 5 + 7 + 13 = 25이므로 중간점은 12.5가 됩니다. 이 지점은 세 번째 세그먼트인 (12, 25) 범위 안에 있으므로 정답은 3입니다.

해결 접근 방식

이 문제는 다음과 같은 방식으로 해결할 수 있습니다. 먼저 모든 선분 길이의 합(arrSum)을 구한 뒤, 중간점을 arrSum / 2로 계산합니다. 이후 선분 길이를 하나씩 누적해 가면서 중간점이 특정 선분의 시작점이나 끝점과 정확히 일치하면 -1을 출력하고, 그렇지 않고 중간점이 어떤 선분의 내부에 있다면 해당 세그먼트의 번호를 출력하면 됩니다.

위 접근 방식의 작동 과정을 보여주는 프로그램입니다.

예시

#include <iostream>
using namespace std;
int findSegmentWithMidPoint(int n, int m, int segment_length[]) {
    double centerPoint = (1.0 * n) / 2.0;
    int sum = 0;
    int segment = 0;
    for (int i = 0; i < m; i++) {
        sum += segment_length[i];
        if ((double)sum == centerPoint) {
            segment = -1;
            break;
        }
        if (sum > centerPoint) {
            segment = i + 1;
            break;
        }
    }
    return segment;
}
int main() {
    int m = 3;
    int segment_length[] = { 5, 7, 13 };
    int arrSum = 0;
    for(int i = 0; i < m; i++)
        arrSum += segment_length[i];
    int ans = findSegmentWithMidPoint(arrSum, m, segment_length);
    cout << "중간점이 위치한 세그먼트 번호는 " << ans;
    return 0;
}

출력

중간점이 위치한 세그먼트 번호는 3