白俊解答-架橋1010回

📜 理解问题

元で都市の市長になった.この町には町を東と西に分ける大きな直線形の川が流れている.しかし元知では橋がないため、市民たちが川を渡るのに大きな不便があったため、橋を建てることにした.川沿いに橋を建てるのに適した場所をウェブサイトと言います.元で江辺をよく調べたところ、江西にはNのサイトがあり、東にはMのサイトがあることが分かった.(N ≤ M)
元は西のサイトと東のサイトを橋につなぎたいと思っています.(1つのサイトには最大1つのブリッジしか接続できません.)元ではできるだけ多くの橋を建てたいので、西のサイト数に応じて(N個)橋を建てたいです.足が重ならないと言ったら、橋を建てることができれば、足の数を計算することができます.

💡 問題の再定義

MからN個の組合せ数を出力する.

▼▼▼計画作成

この問題は組合せ問題と考えられる.
河西をN,河東をMと呼ぶと,M個の元素から任意の順序でN個を選択するMCNを満たす.したがって,いくつの組合せ数があるかを決定するだけでよいが,複数のテストケースが存在するため,動的プログラミングを用いて繰返し計算を阻止する.
組み合わせの問題では、次の性質を満たします.

nC0=nCn=1.

nCr=n-1Cr-1+n-1Cr.

上記の性質を満たす再帰関数を実現して問題を解決すればよい.

💻 計画の実行

dp = []


def combinations(n, r):
    # 이미 구한 값이라면
    if dp[n][r] > 0:
        return dp[n][r]

    # base case
    if r == 0 or n == r:
        dp[n][r] = 1
        return dp[n][r]

    # combinations 구하기
    dp[n][r] = combinations(n - 1, r - 1) + combinations(n - 1, r)

    return dp[n][r]


if __name__ == '__main__':
    T = int(input())
    dp = [[0 for _ in range(30)] for _ in range(30)]
    for _ in range(T):
        N, M = map(int, input().split())
        print(combinations(M, N))

🤔 振り返る

統計学の組合せと動的プログラミングを知ってこそ解決できる問題である.