문자열 S가 주어졌다고 가정해 봅시다. 이 문자열은 {'D', 'I'} 집합에 속한 문자들로만 구성되어 있습니다. 여기서 D는 "감소(decreasing)"를, I는 "증가(increasing)"를 의미합니다.
유효한 순열(valid permutation)은 정수 {0부터 n}으로 이루어진 순열 P[0], P[1], ..., P[n] 중에서 모든 i에 대해 다음 규칙을 만족하는 순열을 말합니다.
S[i] == 'D'라면, P[i] > P[i+1]을 만족해야 합니다.
S[i] == 'I'라면, P[i] < P[i+1]을 만족해야 합니다.
우리가 구해야 할 것은 이러한 유효한 순열의 총개수입니다. 답은 매우 커질 수 있으므로, 결과는 10^9 + 7로 나눈 나머지(mod) 형태로 반환합니다.
예를 들어 입력이 "IDD"라면 출력은 3입니다. 즉, 다음과 같은 세 가지 서로 다른 순열이 존재합니다.
- (0, 3, 2, 1)
- (1, 3, 2, 0)
- (2, 3, 1, 0)
문제 해결 접근 방식
이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 단계에서 가능한 마지막 값의 위치별 경우의 수를 누적하는 것입니다.
알고리즘 단계
n := 문자열 S의 길이
(n + 1) × (n + 1) 크기의 2차원 배열 dp를 선언합니다.
j := 0부터 j <= n까지 반복하며 dp[0][j] := 1로 초기화합니다.
i := 0부터 i < n까지 반복합니다.
S[i]가 'I'인 경우:
j := 0, curr := 0부터 시작하여 j < n - i인 동안 j를 1씩 증가시키며 반복합니다.
curr := (dp[i][j] + curr) mod m
dp[i + 1][j] = (dp[i + 1][j] + curr)
S[i]가 'D'인 경우:
j := n - i - 1, curr := 0부터 시작하여 j >= 0인 동안 j를 1씩 감소시키며 반복합니다.
curr := (dp[i][j + 1] + curr) mod m
dp[i + 1][j] = (dp[i + 1][j] + curr)
최종적으로 dp[n][0]을 반환합니다.
C++ 구현 예제
아래 코드를 통해 실제 구현 방법을 더 자세히 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
class Solution {
public:
int numPermsDISequence(string S) {
int n = S.size();
vector<vector<int>> dp(n + 1, vector<int>(n + 1));
for (int j = 0; j <= n; j++)
dp[0][j] = 1;
for (int i = 0; i < n; i++) {
if (S[i] == 'I') {
for (int j = 0, curr = 0; j < n - i; j++) {
curr = (dp[i][j] + curr) % m;
dp[i + 1][j] = (dp[i + 1][j] + curr) % m;
}
} else {
for (int j = n - i - 1, curr = 0; j >= 0; j--) {
curr = (dp[i][j + 1] + curr) % m;
dp[i + 1][j] = (dp[i + 1][j] + curr) % m;
}
}
}
return dp[n][0];
}
};
main(){
Solution ob;
cout << (ob.numPermsDISequence("IDD"));
}입력
"IDD"
출력
3
마무리
이 문제의 시간 복잡도는 O(n²)이며, 공간 복잡도 역시 O(n²)입니다. DP 테이블을 활용해 'I'(증가)와 'D'(감소) 조건에 따라 누적 합을 방향성 있게 처리하는 것이 핵심 포인트입니다. 접두사 합(prefix sum) 기법을 응용하면 각 단계의 전이를 깔끔하게 처리할 수 있어, 유사한 순열 계산 문제에도 널리 활용되는 패턴입니다.