C++로 정N각형에서 세 번째 사람의 최적 위치 찾기

이 튜토리얼에서는 정N각형(regular N-sided polygon) 위에서 세 번째 사람이 서야 할 최적의 위치를 구하는 방법을 알아보겠습니다.

문제 개요

변의 개수가 N인 정N각형이 주어져 있고, 이미 두 명의 사람이 서로 다른 두 꼭짓점(A, B)에 서 있다고 가정해 보겠습니다. 우리의 목표는 세 번째 사람을 배치할 꼭짓점을 찾되, 기존 두 사람과 세 번째 사람 사이의 거리 합이 최소가 되도록 하는 것입니다.

해결 방법

이 문제는 모든 꼭짓점을 하나씩 확인하는 완전 탐색(brute force) 방식으로 간단하게 해결할 수 있습니다. 알고리즘의 단계는 다음과 같습니다.

N과 두 사람의 위치 A, B를 초기화합니다.
세 번째 사람의 위치를 저장할 변수와 최소 거리 합을 저장할 변수를 초기화합니다.
1부터 N까지 반복하면서 다음을 수행합니다.
- 현재 위치가 A 또는 B라면 이미 사람이 있으므로 건너뜁니다.
- 현재 위치와 A, B 사이의 거리(절댓값 차이)의 합을 계산합니다.
- 계산된 합이 기존 최소 합보다 작으면 위치와 최소 합을 갱신합니다.
반복이 끝나면 세 번째 사람의 위치를 출력합니다.

예제 코드

위 알고리즘을 C++로 구현한 코드입니다.

#include <bits/stdc++.h>
using namespace std;

int findThirdPersonStandingVertex(int N, int A, int B) {
    int position = 0;
    int minimum_sum = INT_MAX, sum;
    for (int i = 1; i <= N; i++) {
        // 이미 사람이 있는 꼭짓점은 건너뜀
        if (i == A || i == B) {
            continue;
        }
        else {
            // 현재 꼭짓점에서 A, B까지의 거리 합
            sum = abs(i - A) + abs(i - B);
            // 현재 합이 기존 최소 합보다 작은지 확인
            if (sum < minimum_sum) {
                // 최소 합과 꼭짓점 위치 갱신
                minimum_sum = sum;
                position = i;
            }
        }
    }
    return position;
}

int main() {
    int N = 7, A = 5, B = 7;
    cout << "Vertex: " << findThirdPersonStandingVertex(N, A, B) << endl;
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

Vertex: 6

결과 분석

N = 7, A = 5, B = 7인 경우를 살펴보겠습니다. 꼭짓점 6을 선택하면 거리 합은 |6 − 5| + |6 − 7| = 1 + 1 = 2로, 어떤 다른 꼭짓점보다도 작습니다. 따라서 세 번째 사람은 꼭짓점 6에 서는 것이 가장 유리합니다.

이 알고리즘의 시간 복잡도는 O(N)으로, 꼭짓점 개수에 비례하여 선형적으로 증가하기 때문에 매우 효율적입니다.

마무리

이번 튜토리얼에서는 정N각형 위에서 두 사람과의 거리 합이 최소가 되는 세 번째 사람의 위치를 찾는 방법을 배웠습니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.