문제 개요
처음 n개의 자연수(1부터 n까지)로 이루어진 배열 A가 있다고 가정해 보겠습니다. 이때 구해야 할 것은 다음 두 가지 값입니다.
- S1: 배열 A에 정확히 k번의 인접 스왑(adjacent swap)을 수행한 후 만들 수 있는 서로 다른 시퀀스의 개수
- S2: 배열 A에 최대 k번의 스왑(임의의 두 원소 교환 허용)을 수행한 후 만들 수 있는 서로 다른 시퀀스의 개수
여기서 인접 스왑이란 인덱스 i와 i+1에 위치한 두 원소를 맞교환하는 연산을 의미합니다.
예제로 이해하기
n = 3, k = 2가 입력으로 주어진 경우를 살펴보겠습니다. 원래 배열은 [1, 2, 3]입니다.
- 정확히 2번의 인접 스왑 후: [1, 2, 3], [2, 3, 1], [3, 1, 2]를 만들 수 있으므로 S1 = 3입니다.
- 최대 2번의 스왑 후:
- 0번 스왑: [1, 2, 3]
- 1번 스왑: [2, 1, 3], [3, 2, 1], [1, 3, 2]
- 2번 스왑: [1, 2, 3], [2, 3, 1], [3, 1, 2]
중복을 제외하면 총 6가지이므로 S2 = 6입니다.
따라서 출력은 3, 6이 됩니다.
풀이 접근 방법
n이 커지면 완전 탐색으로는 감당할 수 없으므로, 동적 계획법(DP)을 활용해야 합니다. 문제는 크게 두 부분으로 나누어 생각할 수 있습니다.
1. 정확히 k번의 인접 스왑 (S1)
인접 스왑 한 번은 시퀀스의 반전(inversion) 개수를 정확히 1씩 증가 또는 감소시킵니다. 따라서 어떤 순열이 정확히 k번의 인접 스왑으로 도달 가능하려면, 그 순열의 반전 개수 x가 k 이하이면서 k와 같은 홀짝성(parity)을 가져야 합니다. 남은 스왑 횟수는 같은 위치를 앞뒤로 반복해서 바꿈으로써 소진할 수 있기 때문입니다.
길이 n의 순열 중 반전 개수가 정확히 x인 순열의 수를 M(n, x)라 하면 다음 점화식이 성립합니다.
M(n, x) = M(n, x−1) + M(n−1, x) − M(n−1, x−n)
코드의 배열 A가 이 값을 관리하며, 최종적으로 A[k%2 : k+1 : 2] 구간의 합, 즉 k 이하에서 k와 홀짝이 같은 모든 반전 개수에 해당하는 경우의 수를 더해 S1을 구합니다.
2. 최대 k번의 임의 스왑 (S2)
임의의 두 원소를 맞바꾸는 일반 스왑의 경우, 순열을 정렬 상태로 되돌리는 데 필요한 최소 스왑 횟수는 '원소 개수 − 사이클 개수'로 알려져 있습니다. 코드의 배열 C는 '최대 j번의 스왑으로 만들 수 있는 길이 n 순열의 수'를 저장하며, 다음 점화식으로 갱신됩니다.
C(n, j) = C(n−1, j) + (n−1) × C(n−1, j−1)
첫 번째 항은 새 원소 n이 자기 자리에 그대로 고정된 경우이고, 두 번째 항은 첫 스왑에서 n이 나머지 n−1개 원소 중 하나와 맞교환되는 경우를 의미합니다. 최종 답은 C(min(n−1, k))입니다.
계산 값이 매우 커질 수 있으므로 모든 연산은 10^9 + 7로 나눈 나머지를 사용합니다.
구현 코드
아래는 위 접근 방식을 파이썬으로 구현한 예제입니다.
p = 10**9+7
def solve(n, k):
A = [1]
C = [1]
for n in range(2, n+1):
B = A
A = [1]
D = C
C = [1]
# 반전 개수별 순열의 수(Mahonian 수) 갱신
for x in range(1, min(k+1, n*(n-1)//2 + 1)):
A.append((A[-1]
+ (B[x] if x < len(B) else 0)
- (B[x-n] if 0 <= x-n else 0)) % p)
# 최대 스왑 횟수별 도달 가능 순열의 수 갱신
for x in range(1, n-1):
C.append((D[x] + (n-1)*D[x-1]) % p)
C.append(n * D[-1] % p)
return sum(A[k%2:k+1:2]) % p, C[min(n-1, k)]
n = 3
k = 2
print(solve(n, k))실행 결과
입력:
n = 3, k = 2
출력:
(3, 6)
마무리
이 풀이의 시간 복잡도는 대략 O(n × k)이며, 두 개의 1차원 배열만 유지하면 되므로 공간 복잡도 역시 O(k) 수준으로 효율적입니다. 인접 스왑 문제는 '반전 개수', 일반 스왑 문제는 '사이클 분해'라는 핵심 아이디어만 잡으면 점화식을 깔끔하게 세울 수 있다는 점을 기억해 두면 유사한 조합론 문제를 풀 때 큰 도움이 됩니다.