C++로 순열 추측에 필요한 이동 횟수 계산하기

자연수 N이 주어졌을 때, 최악의 경우 순열(permutation)을 완전히 추측하는 데 필요한 이동 횟수를 구하는 것이 이 글의 목표입니다. 순열의 각 위치를 차례대로 확인하며 가능한 모든 경우를 고려하면, 필요한 총 이동 횟수는 아래와 같은 규칙으로 계산할 수 있습니다.

핵심 아이디어는 간단합니다. 1부터 n까지의 각 i에 대해 i × (n − i)를 모두 더한 뒤, 마지막에 n을 한 번 더해 주면 됩니다.

예시

입력:

9

출력:

129

n이 9일 때 각 항을 계산하면 8 + 14 + 18 + 20 + 20 + 18 + 14 + 8 + 0 = 120이 되고, 여기에 n인 9를 더해 최종 결과인 129를 얻습니다.

알고리즘

1. 숫자 n을 초기화합니다.
2. count를 0으로 초기화합니다.
3. i를 1부터 n까지 반복하는 루프를 작성합니다.
   • 매 반복마다 count에 i × (n − i)를 더합니다.
4. 루프가 끝나면 count에 n을 더합니다.
5. count를 반환합니다.

수학적 분석

위 과정은 등차수열의 합 공식을 활용해 닫힌 형태(closed form)로 정리할 수 있습니다.

Σ i(n − i) = n · n(n+1)/2 − n(n+1)(2n+1)/6 = n(n² − 1)/6 = (n³ − n)/6

따라서 전체 이동 횟수는 (n³ − n) / 6 + n입니다. n = 9를 대입하면 (729 − 9) / 6 + 9 = 120 + 9 = 129로, 실제 코드 실행 결과와 일치합니다.

C++ 구현

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

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

int getNumberMoves(int n) {
    int count = 0;
    for (int i = 1; i <= n; i++) {
        count += i * (n - i);
    }
    count += n;
    return count;
}

int main() {
    int n = 9;
    cout << getNumberMoves(n) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과를 얻습니다.

129

시간 복잡도

루프가 1부터 n까지 한 번만 실행되므로 시간 복잡도는 O(n)입니다. 참고로 n이 커지면 결과값이 int 범위를 빠르게 초과할 수 있으므로, 입력 크기가 큰 경우에는 long long 타입을 사용하는 것이 안전합니다.