[SWEA] 19189 순열의 아름다움

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AYzIcBsq_agDFAQ9&categoryId=AYzIcBsq_agDFAQ9&categoryType=CODE&&&

SW Expert Academy

 

 

접근

• 여러 가지 접근이 있는데 필자가 접근한 단계로 차근차근 진행해 보도록 하겠다.

 

BruteForce 구현

• 모든 경우의 수를 구해야 하는데... 문제를 보면 $1 \leq N \leq 250000$ 이다.
• 우리가 찾는 아름다운 쌍을 찾기 위해서는 먼저 $250000!$ 개의 행들을 훑어야 하는데 당연히 시간복잡도는 $O(N!)$ 이상이고, 이 방법은 전혀 좋지 않다.

 

2차원 DP 구현

• 예제를 통해 계산해보면서 확인해보자.
• 우선 DP table이 무엇을 나타낼 것인지를 정의해야 하는데 필자는 $DP[i][j] = (r - l)가 j인 경우의 수$ 로 정의하였다.
  • 예를 들어 $N=3$ 일때는 다음과 같은 순열들이 나올 수 있다.

1, 2, 3    2, 1, 3
1, 3, 2    2, 3, 1
3, 1, 2    3, 2, 1

 

 

• $r - l = 0$ 일 때.
  • $r - l = 0$ 이면 $ r = l $을 만족한다. $ r = l$ 이면 $\max(pl, pr) - \min(pl, pr) = 0$ 이 되므로 길이 1인 모든 수가 아름다운 쌍이 될 수 있다.
  • 이때 아름다운 수의 개수는 $N! \times N$개 임이 자명하다.
    • 증명) $N$개의 수에 대한 순열은 $N!$개 이고, 이 각각의 순열마다 1부터 $N$까지의 수가 존재하므로 전체 개수는 $N! \times N$ 개 이다.
• $r - l = N - 1$ 일 때
  • $r - l = N - 1$ 인 것은 전체 범위를 대상으로 최대값과 최소값을 뺀 결과임을 의미한다. 전체 범위에서 항상 최소값은 1이 되고 최대값은 $N$이 되므로 전체 범위에서는 모든 순열이 $r - l = N - 1$ 일 때 아름다운 쌍이 될 수 있다.
  • 이때 아름다운 수의 개수는 순열의 개수인 $N!$개 이다.
• 그 이외
  • 위의 그림을 유심히 확인해보자. 무언가 규칙성이 보이지 않는가?
  • 신기하게도, 아래쪽의 수들은 자신의 좌측 상단의 수에서 열 별로 각각 2부터 $N$까지 곱한 것을 확인할 수 있다.
  • 따라서 우리는 맨 처음 수를 제외하고, 점화식을 만들어낼 수 있다. 이때 점화식은 다음과 같다. $dp[i][j] = dp[i - 1][j - 1] \times j$
  • 맨 처음 수 $dp[i][0]$은 맨 위의 길이 $ r - l = 0 $ 일 때를 의미하므로 $ dp[i][0]  = N! \times N$ 로 할 수 있다.
• 위의 정리들을 통해서 점화식을 통해 진행할 수 있다.
• 이때 시간 복잡도는 $O(N^2)$가 되며 공간 복잡도의 경우에도 $O(N^2)$가 되나 sliding window와 같은 테크닉을 사용하면 $O(1)$ 정도에서 마무리될 것 같기도 하다.

 

1차원 DP

• 위의 정리는 정답을 명쾌하게 해주기 때문에 좋은 해답이나 $N = 250000$ 이라는 조건 때문에 $O(N^2)$일 경우 시간초과가 나게 된다. 따라서 조금 더 최적화 해줄 필요가 있다.
• 지금까지는 계산의 결과를 가지고 생각했지만 위의 표를 다시 재구성하면 다음과 같이 만들어 볼 수 있다.

• 이를 잘 관찰하면 다음과 같은 일반화된 식을 얻을 수 있다.
  • $dp[N][0] = N! \times N \times 1$
  • $dp[N][1] = (N - 1)! \times (N - 1) \times 1 \times 2$
  • $dp[N][2] = (N - 2)! \times (N - 2) \times 1 \times 2 \times 3$
  • ...
  • $dp[N][N - 1] = 1! \times 1 \times 2 \times ... \times N$
• 우리가 원하는 답은 $N$에서 얻을 수 있는 모든 아름다운 쌍의 합이므로 table 상에서 1부터 N까지를 싹 더해주면 된다. 위의 식들은 일반화가 가능한데 다음과 같이 만들 수 있다.
  • $dp[N][k] = (N - k)! \times (N - k) \times (k + 1)!, (k=0, 1, 2, ..., N - 1)$
• 따라서 답 $ans$는 다음과 같이 표현될 수 있다.
  • $ans = \sum_{k=0}^{N-1} \{(N - k)! \times (N - k) \times (k + 1)!\}  $
• 이제 이를 반복문으로 계산하면 되는데 문제는 $(N - k)!$와 $(k + 1)!$ 의 펙토리얼 계산이 시간을 잡아먹을 수 있다. 수식을 잘 분석하면 $(N - k)$와 $(k + 1)$은 각각 $N$ 부터 $1$, $1$ 부터 $N$까지로 결국 $1$ 부터 $N$까지의 모든 펙토리얼을 다 구해야 한다는 것을 알 수 있다.
• 따라서 답에 대한 dp를 계산하는 대신 펙토리얼 계산 결과를 dp로 해서 접근하도록 하면 1차원 dp와 일반항으로 문제를 해결할 수 있다.(물론 소수로 나눈 나머지 관리는 해줘야 한다.)
• 펙토리얼의 경우 $dp[i] = dp[i - 1] \times i$로 매우 쉽게 구할 수 있다.
• 해당 방식의 시간복잡도는 $O(N)$으로 dp를 구하는데 1 ~ $N$ 까지 한 번, 답 구하는데 N - 1 ~ 0 까지 한 번으로 $N = 250000$ 이더라도 매우 쾌적하게 문제가 해결되는 것을 볼 수 있다.

 

 

답안 코드

import java.util.*;
import java.io.*;
 
public class Solution {
 
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
         
        for(int test_case = 1; test_case <= T; test_case++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
             
            int N = Integer.parseInt(st.nextToken());
            int P = Integer.parseInt(st.nextToken());
             
            int sum = 0;
            long[] facto = new long[N + 1];
            facto[1] = 1;
             
            for(int i = 2; i <= N; i++) {
                facto[i] = (facto[i - 1] * i) % P;
            }
             
            for(int i = N - 1; i >= 0; i--) {
                sum += (((facto[N - i] * (N - i)) % P) * facto[i + 1]) % P;
                sum %= P;
            }
             
            System.out.println("#" + test_case + " " + sum);
        }
    }
}