[백준 20152] Game Addiction

조합론 문제

www.acmicpc.net/problem/20152

[문제 풀이]

(N, N)에서 (M, M)으로 가는 최단경로의 개수 중, $y <= x$ 인 경로의 개수를 출력하는 문제입니다.

다이나믹 프로그래밍으로도 풀이할 수 있습니다.

dp풀이를 간략하게 설명하자면 (N, N)에서 시작하여 오른쪽 위 방향으로 이동한다 가정했을 때, 2차원 dp테이블을 만들어 줍니다. 물론 $y > x$는 사용하지 않습니다.

(N, N) 지점의 dp테이블 값을 0으로 설정한 뒤, 오른쪽 위로 이동하면서 dp테이블의 값을 (왼쪽의 dp테이블 값) + (아래쪽의 dp테이블 값)으로 설정해주면 풀이가 가능합니다.

점화식으로는 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]입니다.

그러나 이 문제는 조합으로도 풀이가 가능합니다.

우선, $y > x$인 부분을 사용하지 않는다는 조건이 없었다면 더 쉬운 문제입니다.

높이가 h고 너비가 w인 2차원 평면에서 양 끝점으로 이동하는 최단 경로의 개수는 $\dbinom{h + w}{h}$입니다.

해당 문제에 위의 사실을 이용한다면 $\dbinom{2n}{n} (n = |N - H|)$로 풀이가 가능합니다.

하지만 $y > x$를 사용하지 않으므로 위보다는 조금 어렵게 풀이해야 합니다.

카탈란 수열이라는 개념을 사용한다면 이 문제를 해결할 수 있습니다.

카탈란 수열에 관한 내용은 위 링크에서 매우 잘 설명하였습니다.

카탈란 수열의 일반항인 $\dfrac{1}{n +1} \dbinom{2n}{n} $를 사용하여도 좋고 점화식을 사용하여도 좋습니다.

파이썬의 math모듈은 팩토리얼 연산을 지원하므로 파이썬으로 카탈란 수열의 일반항을 이용하여 답을 출력할 수 있습니다.

해당 문제에 일반항을 적용할 때는 (N, N)과 (H, H)가 양 끝점이 되도록 n = $|N - H|$로 하고 n에 대한 카탈란 수를 구해야 합니다.

[소스 코드] / Python 3

import math
n, m = map(int, input().split())
n -= m
n = abs(n)
m = math.factorial
print(m(2 * n) // m(n) // m(n) // (n+1))

5525호 LAB실