C++에서 주어진 원의 두 부분 사이 최소 각도 차이를 찾는 프로그램

이 문제에서는 원을 이루는 각 조각의 각도가 담긴 배열이 주어집니다. 우리의 목표는 C++에서 주어진 원의 두 부분 사이의 가장 작은 각도 차이를 찾는 프로그램을 작성하는 것입니다.

문제 설명

원을 구성하는 모든 조각의 각도가 배열 형태로 주어집니다. 이 조각들을 연속된 형태로만 합쳐서 두 개의 부분을 만들 때, 두 부분의 각도 차이가 최소가 되도록 만들어야 합니다.

예제로 문제 이해하기

입력

ang[] = {90, 45, 90, 135}

출력

90

설명

1번째와 2번째 조각을 합치면 90 + 45 = 135가 됩니다.

3번째와 4번째 조각을 합치면 90 + 135 = 225가 됩니다.

두 부분의 차이 = 225 − 135 = 90

해결 접근 방법

여기서 중요한 점은 모든 조각을 합쳐 정확히 두 개의 부분을 만들어야 하며, 반드시 연속된 조각들끼리 묶어야 한다는 것입니다. 즉, 위 예제에서 1번째와 3번째 조각을 함께 묶을 수는 없습니다.

첫 번째 부분의 각도를 A라고 해보겠습니다.

그렇다면 두 번째 부분의 각도는 자동으로 360 − A가 됩니다.

따라서 두 부분의 각도 차이는 |A − (360 − A)| 입니다. 각도는 음수가 될 수 없으므로 절댓값을 사용합니다.

이 식을 정리하면 다음과 같습니다.

2 × |A − 180|

결국 이 값이 최소가 되도록 만들면 됩니다. 이를 위해 원의 조각들을 가능한 모든 연속 조합으로 묶어보면서 2 × |A − 180|의 최솟값을 찾으면 됩니다.

해결 방법의 동작을 보여주는 프로그램

예제 코드

#include <iostream>
#include <math.h>
using namespace std;
int CalcSmallDiffAng(int ang[], int n) {
    int Left = 0, A = 0, minDiff = 360;
    for (int i = 0; i < n; i++) {
        A += ang[i];
        while (A >= 180) {
            minDiff = min(minDiff, 2 * abs(180 - A));
            A -= ang[Left];
            Left++;
        }
        minDiff = min(minDiff, 2 * abs(180 - A));
    }
    return minDiff;
}
int main() {
    int ang[] = { 90, 45, 90, 135 };
    int n = sizeof(ang) / sizeof(ang[0]);
    cout<<"The smallest difference of angles of two parts of a given
    circle is "<<CalcSmallDiffAng(ang, n);
    return 0;
}

출력 결과

The smallest difference of angles of two parts of a given circle is 90

위 코드는 투 포인터(two pointer) 기법을 활용해 누적 각도 A가 180 이상이 될 때마다 왼쪽 조각을 하나씩 제거하면서 가능한 모든 분할 지점을 효율적으로 탐색합니다. 이 방식의 시간 복잡도는 O(n)으로, 조각의 개수가 많아져도 빠르게 최소 각도 차이를 구할 수 있습니다.