C++로 원 위에서 정반대 위치에 있는 사람 찾기

이 문제에서는 두 개의 정수 N과 M이 주어집니다. 원 위에 N명의 사람이 서 있고, M은 그중 한 사람의 위치를 나타냅니다. 우리의 목표는 M 위치에 있는 사람과 정반대(마주 보는) 위치에 있는 사람의 위치를 구하는 것입니다.

문제 이해하기

예시를 통해 문제를 살펴보겠습니다.

입력 − N = 6, M = 3

출력 − 6

설명 − 원 위에 6명의 사람이 있을 때, 3번 위치에 있는 사람의 정반대는 6번 위치입니다.

해결 방법

이 문제를 해결하려면 두 가지 경우를 고려해야 합니다. 위치가 원의 절반보다 크면(후반부) 정반대 위치는 전반부에 있고, 그 반대의 경우도 마찬가지입니다.

이를 수학적으로 공식화하면 다음과 같습니다.

• 경우 1 − m > n/2 인 경우, 정반대 위치 = m − (n/2)
• 경우 2 − m ≤ n/2 인 경우, 정반대 위치 = m + (n/2)

구현 예제

위 해결 방법을 보여주는 프로그램입니다.

#include <iostream>
using namespace std;
void printOppositePosition(int n, int m) {
    int pos;
    if (m > (n / 2))
        pos = (m - (n / 2));
    else
        pos = (m + (n / 2));
    cout << pos;
}
int main() {
    int N = 8, M = 4;
    cout << "원 위에 " << N << "명이 서 있을 때 " << M << "번 위치의 사람과 마주 보는 사람의 위치는 ";
    printOppositePosition(N, M);
    return 0;
}

출력 결과

원 위에 8명이 서 있을 때 4번 위치의 사람과 마주 보는 사람의 위치는 8

정리

이 알고리즘은 단순한 조건문 하나와 나눗셈 연산만 사용하므로 시간 복잡도는 O(1)입니다. 원형 배치에서 정반대 위치는 항상 현재 위치에서 인원수의 절반(n/2)만큼 떨어져 있다는 핵심 아이디어만 기억하면 됩니다. 다만 n이 홀수일 경우에는 정확히 마주 보는 사람이 존재하지 않으므로, 이 공식은 n이 짝수일 때 가장 잘 동작한다는 점을 유의하세요.