Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 계산하는 유효한 픽업·배송 순서의 모든 경우의 수

n개의 주문 목록이 있으며, 각 주문에는 하나의 픽업(Pickup)과 하나의 배송(Delivery) 서비스가 포함되어 있다고 가정해 보겠습니다. 이 문제의 목표는 배송[i]이 반드시 픽업[i]보다 뒤에 위치하도록 만들 수 있는 모든 유효한 순서(시퀀스)의 개수를 구하는 것입니다. 결과값이 매우 커질 수 있으므로 109 + 7로 나눈 나머지를 반환합니다.

예시로 이해하기

입력이 2인 경우를 살펴보겠습니다. 이때 정답은 6이며, 가능한 모든 유효한 순서는 다음과 같습니다.

  • (P1, P2, D1, D2)
  • (P1, P2, D2, D1)
  • (P1, D1, P2, D2)
  • (P2, P1, D1, D2)
  • (P2, P1, D2, D1)
  • (P2, D2, P1, D1)

반면 (P1, D2, P2, D1)은 픽업 2(P2)가 배송 2(D2)보다 늦게 등장하기 때문에 유효하지 않습니다.

풀이 접근 방법

이 문제는 메모이제이션(memoization)을 활용한 동적 계획법(DP)으로 효율적으로 해결할 수 있습니다. 상태는 두 변수로 관리합니다.

  • i: 아직 픽업하지 않은 남은 주문의 수
  • j: 픽업은 완료되었지만 아직 배송되지 않은 주문의 수

각 단계에서는 두 가지 선택이 가능합니다.

  • 픽업 수행: 남은 주문 중 하나를 픽업합니다. 선택 가능한 경우의 수는 현재 남은 주문 수(left)이며, 이후 상태는 (i-1, j)로 전환됩니다.
  • 배송 수행: 픽업이 완료된 주문 중 하나를 배송합니다. 선택 가능한 경우의 수는 진행 중인 픽업 수(inPickup)이며, 이후 상태는 (i, j-1)로 전환됩니다.

여기서 j > i 조건은 "배송 대기 중인 주문이 존재한다"는 사실을 보장합니다. 덕분에 배송이 자신의 픽업보다 먼저 발생하는 잘못된 경우가 자연스럽게 배제됩니다.

알고리즘 단계

  • m := 109 + 7 (모듈로 상수)
  • N := 550 (최대 크기)
  • 크기가 (N+5) × (N+5)인 배열 dp를 선언하고 -1로 초기화합니다.
  • 함수 add(a, b): ((a mod m) + (b mod m)) mod m을 반환합니다.
  • 함수 mul(a, b): ((a mod m) × (b mod m)) mod m을 반환합니다.
  • 함수 solve(inPickup, left, i, j):
    • i = 0이고 j = 0이면 1을 반환합니다.
    • dp[i][j] != -1이면 이미 계산된 값 dp[i][j]를 반환합니다.
    • ret := 0으로 초기화합니다.
    • i > 0이면 ret := add(ret, mul(left, solve(inPickup + 1, left - 1, i - 1, j)))로 갱신합니다.
    • j > i이면 ret := add(ret, mul(inPickup, solve(inPickup - 1, left, i, j - 1)))로 갱신합니다.
    • dp[i][j] = ret을 저장한 뒤 반환합니다.
  • 메인 함수에서는 solve(0, n, n, n)을 호출하여 최종 결과를 얻습니다.

C++ 구현 예제

아래 코드를 통해 실제 구현을 더 쉽게 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int m = 1e9 + 7;
const int N = 550;
int dp[N + 5][N + 5];
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:
    void pre(){
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                dp[i][j] = -1;
            }
        }
    }
    int solve(int inPickup, int left, int i, int j){
        if (i == 0 && j == 0)
        return 1;
        if (dp[i][j] != -1)
        return dp[i][j];
        int ret = 0;
        if (i > 0) {
            ret = add(ret, mul(left, solve(inPickup + 1, left - 1, i
            - 1, j)));
        }
        if (j > i) {
            ret = add(ret, mul(inPickup, solve(inPickup - 1, left, i,
            j - 1)));
        }
        return dp[i][j] = ret;
    }
    int countOrders(int n){
        pre();
        return solve(0, n, n, n);
    }
};
main(){
    Solution ob;
    cout << (ob.countOrders(2));
}

입력

2

출력

6

복잡도 분석

시간 복잡도와 공간 복잡도는 모두 O(n²)입니다. 메모이제이션 덕분에 동일한 상태 (i, j)에 대한 중복 계산이 제거되어 효율성이 크게 향상됩니다. 참고로 이 문제는 조합론적으로 (2n)! / 2n의 닫힌 형태로도 표현할 수 있지만, n이 커질 때 오버플로우를 방지하려면 위와 같이 모듈러 연산 기반의 DP 접근 방식이 훨씬 안전합니다.