처음 n개의 자연수로 이루어진 배열 A와 이 배열의 한 순열 P{p1, p2, ..., pn}가 있다고 가정해 봅시다. 이때 주어진 조건을 만족하는 '매직 세트(magic set)' 순열이 총 몇 개인지 구해야 합니다. 하나의 순열이 다음 두 규칙을 모두 만족할 때 매직 세트라고 정의합니다.
- k가 주어지면, 위치 a[1], a[2], ..., a[k]에 있는 원소는 양쪽 인접 원소보다 작아야 합니다. 즉, P[a[i]-1] > P[a[i]] < P[a[i]+1]
- l이 주어지면, 위치 b[1], b[2], ..., b[l]에 있는 원소는 양쪽 인접 원소보다 커야 합니다. 즉, P[b[i]-1] < P[b[i]] > P[b[i]+1]
예를 들어 입력이 n = 4, k = 1, l = 1, k_vals = [2], l_vals = [3]이라면 출력은 5입니다. N = 4에서 a[1] = 2, b[1] = 3이므로 [2,1,4,3], [3,2,4,1], [4,2,3,1], [3,1,4,2], [4,1,3,2]의 다섯 가지 순열만 조건을 만족하기 때문입니다.
접근 방법
가능한 모든 순열을 일일이 생성하면 매우 비효율적입니다. 대신 동적 계획법(DP)과 누적 합(prefix sum) 기법을 활용하면 O(n²) 시간 안에 문제를 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 오버플로를 방지하기 위해 모듈러 상수 MOD := 10^9+7을 정의합니다.
- 크기 n+2의 배열 F를 0으로 초기화한 뒤, k_vals의 각 위치 a에는 1(국소 최솟값), l_vals의 각 위치 b에는 -1(국소 최댓값)을 표시합니다. 이때 제약끼리 서로 인접하거나 충돌하면 유효한 배치가 존재하지 않으므로 즉시 0을 반환합니다.
- FF[i] = F[i] - F[i-1]을 계산하여 각 위치에서 요구되는 상승 또는 하강 방향을 결정합니다.
- A[1] = 1에서 시작해 i = 2부터 n까지 반복하면서, 각 i에 대해 마지막 값이 j가 되는 경우의 수를 누적 합으로 갱신하고 A와 B 배열을 교환하며 진행합니다. FF[i] > 0이면 B[j] = (B[j-1] + A[j-1]), FF[i] < 0이면 B[j] = (B[j-1] + A[i-1] - A[j-1]), 그 외에는 B[j] = (B[j-1] + A[i-1])를 사용합니다.
- 최종적으로 A[n]이 조건을 만족하는 순열의 총 개수가 됩니다.
파이썬 구현 예시
def solve(n, k, l, k_vals, l_vals):
p = 10**9+7
F = [0] * (n + 2)
for a in k_vals:
if F[a - 1] == 1 or F[a + 1] == 1:
p = None
F[a] = 1
for b in l_vals:
if F[b] == 1 or F[b - 1] == -1 or F[b + 1] == -1:
p = None
F[b] = -1
if p == None:
return 0
else:
A = [0] * (n + 1)
B = [0] * (n + 1)
FF = [None] * (n + 1)
for i in range(1, n + 1):
FF[i] = F[i] - F[i - 1]
A[1] = 1
for i in range(2, n + 1):
for j in range(1, i + 1):
if FF[i] > 0:
B[j] = (B[j - 1] + A[j - 1]) % p
elif FF[i] < 0:
B[j] = (B[j - 1] + A[i - 1] - A[j - 1]) % p
else:
B[j] = (B[j - 1] + A[i - 1]) % p
A, B = B, A
return A[n]
n = 4
k = 1
l = 1
k_vals = [2]
l_vals = [3]
print(solve(n, k, l, k_vals, l_vals))입력
4, 1, 1, [2], [3]
출력
5