C++로 x번의 인접 스왑 후 두 경쟁 학생 간 최대 거리 구하기

문제 설명

네 개의 숫자 n, x, a, b가 주어진다고 가정해 봅시다. 한 줄에 n명의 학생이 서 있으며, 그중 두 명은 서로 라이벌 관계입니다. 한 학생은 위치 a에, 다른 학생은 위치 b에 서 있습니다. 위치는 왼쪽에서 오른쪽으로 1부터 n까지 번호가 매겨집니다.

우리는 이 두 학생 사이의 거리를 최대한 멀리 만들고자 합니다. 이를 위해 다음 연산을 최대 x번 수행할 수 있습니다.

• 인접한 두 학생을 선택하여 서로 자리를 바꾼다(swap).

x번의 스왑 후 얻을 수 있는 최대 거리를 구하는 것이 목표입니다.

예를 들어 입력이 n = 5, x = 1, a = 3, b = 2라면 출력은 2가 됩니다. 위치 3과 위치 4에 있는 학생을 맞바꾸면 두 학생 사이의 거리는 |4 - 2| = 2가 되기 때문입니다.

해결 접근 방식

이 문제는 아주 간단한 수학적 관찰 하나로 해결할 수 있습니다.

• 스왑 한 번당 두 학생 사이의 거리는 최대 1씩 늘어날 수 있습니다. 따라서 x번의 스왑으로 거리를 최대 |a - b| + x까지 늘릴 수 있습니다.
• 하지만 거리의 물리적 상한은 존재합니다. 한 학생은 위치 1로, 다른 학생은 위치 n으로 보내야 하므로 가능한 최대 거리는 n - 1입니다.

따라서 정답은 두 값 중 작은 쪽입니다.

min(|a - b| + x, n - 1)

예제 코드

아래 C++ 구현을 통해 더 잘 이해해 보겠습니다.

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

int solve(int n, int x, int a, int b) {
    return min(abs(a - b) + x, n - 1);
}

int main() {
    int n = 5;
    int x = 1;
    int a = 3;
    int b = 2;
    cout << solve(n, x, a, b) << endl;
}

입력

5, 1, 3, 2

출력

2

복잡도 분석

이 풀이는 단순히 몇 개의 값에 대한 산술 연산과 비교만 수행하므로 시간 복잡도는 O(1)입니다. 추가적인 자료구조도 필요하지 않아 공간 복잡도 역시 O(1)입니다. n과 x가 매우 크더라도 즉시 답을 계산할 수 있습니다.