leetcode 1359, Count All Valid Pickup and Delivery Options

문제 설명

n 만큼의 주문이 주어졌을 때, 각 주문은 pickup과 delivery 서비스를 포함하고 있다. 모든 가능한 pickup과 delivery를 나열한 경우의 수를 구하여라. 단 delivery(i)는 pickup(i)보다 뒤에 와야 한다. 만일 정답이 너무 커지면 10^9+7로 나누어라.

https://leetcode.com/problems/count-all-valid-pickup-and-delivery-options/

Count All Valid Pickup and Delivery Options - LeetCode

문제 풀이

Hard라고 쓰여 있는 만큼 난이도가 상당했던 문제였다. 모든 경우의 수를 계산한 다음에 해당 경우의 수가 맞는지 안 맞는지 찾는 방식은 일단 불가능하다. n이 최대 500까지 가능해서 깊이가 너무 깊어져 stackOverFlow가 일어날 확률이 높기 때문이다.

 

그러므로 O(n) 방식으로 돌아가는 풀이가 필요한데, 이는 dp로 해결할 수 있다.

 

예를 들어서 n이 2라고 생각해보자.

그렇다면 아래와 같이 빈칸은 총 2*n으로 4일 것이다.

 

_ _ _ _

 

여기서 p1이 위치할 수 있는 경우는 2 * n -1으로 총 3가지 이다. -1을 해주는 이유는 언제나 delivery가 pickup보다 뒤에 와야 하므로 p1이 맨 뒤에 가는 경우는 존재하지 않기 때문이다.

이제 p1과 p2를 나열해보자.

 

p1 p2 _ _

 

이렇게 되면 이제 d1과 d2를 둘 수 있는 곳은 총 n가지 즉,  2가지이다. 때문에 dp의 점화식은 (2 * i -1 ) * i라고 할 수 있다. 또한 이 전의 값을 이용해줘야 하므로 현재의 count에다가 위의 식으로 계산한 값을 곱해줘야 한다.

코드

java

import java.util.*;
import java.io.*;

class Solution {
    public int countOrders(int n) {
        int mod = (int)Math.pow(10, 9) + 7;
        long count = 1;
        for (int i=2; i<=n; i++) {
            count = (count * (2 * i - 1) * i) % mod;
        }

        return (int)count;
    }
}