C++로 배열의 완전 순열(Derangement) 개수 구하기

문제 개요

1부터 n까지의 수가 오름차순으로 나열된 배열이 주어졌을 때, 이 배열로 만들 수 있는 완전 순열(derangement)의 개수를 구하는 것이 목표입니다.

조합수학에서 완전 순열이란 집합의 모든 원소를 재배치하되, 어떤 원소도 원래 자리에 남지 않도록 배치한 순열을 의미합니다. 결과값이 매우 커질 수 있으므로, 최종 답은 10^9 + 7로 나눈 나머지를 반환해야 합니다.

예를 들어 입력이 3이라면 출력은 2입니다. 원래 배열이 [1, 2, 3]일 때 조건을 만족하는 완전 순열은 [2, 3, 1]과 [3, 1, 2] 두 가지뿐입니다.

알고리즘 접근 방법

동적 계획법(DP)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 점화식은 다음과 같습니다.

dp[i] = (i - 1) × (dp[i-1] + dp[i-2])

i번째 원소는 자신을 제외한 (i-1)개의 위치 중 한 곳으로만 이동할 수 있습니다. i번째 원소가 j번째 위치로 갔다고 가정했을 때 두 가지 경우로 나눌 수 있습니다.

j번째 원소가 i번째 위치로 이동하는 경우 → 남은 문제의 경우의 수는 dp[i-2]
j번째 원소가 i번째 위치로 이동하지 않는 경우 → 남은 문제의 경우의 수는 dp[i-1]

두 경우를 합하고 (i-1)가지의 위치 선택을 곱하면 위 점화식이 성립합니다.

구현 단계

m := 10^9 + 7 (모듈러 상수 설정)
add(a, b): ((a mod m) + (b mod m)) mod m 을 반환하는 함수 정의
mul(a, b): ((a mod m) × (b mod m)) mod m 을 반환하는 함수 정의
n이 1이면 0 반환 (원소 하나는 제자리를 벗어날 수 없음)
n이 2이면 1 반환 ([2, 1] 하나뿐)
크기가 (n + 1)인 dp 배열을 선언하고 dp[2] := 1로 초기화
i = 3부터 n까지 반복하며 dp[i] := mul(i - 1, add(dp[i - 2], dp[i - 1])) 계산
dp[n] 반환

C++ 구현 예제

다음 코드를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;

lli add(lli a, lli b){
    return ((a % m) + (b % m)) % m;
}
lli mul(lli a, lli b){
    return ((a % m) * (b % m)) % m;
}
class Solution {
public:
    int findDerangement(int n) {
        if (n == 1)
            return 0;
        if (n == 2)
            return 1;
        vector<lli> dp(n + 1);
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = mul(i - 1, add(dp[i - 2], dp[i - 1]));
        }
        return dp[n];
    }
};
main(){
    Solution ob;
    cout<<(ob.findDerangement(3));
}