무한한 크기의 2차원 격자판이 있다. 성모는 좌측 상단의 점 에 있고, 우측 하단의 에 있는 찬민이를 만나러 가려고 한다. 격자판 위에는 개의 폭탄들이 격자점에 있기 때문에, 성모는 폭탄들을 피해서 이동해야 한다. 성모는 오른쪽, 또는 아래로만 이동할 수 있을 때, 성모가 폭탄을 피해서 찬민이가 있는 곳까지 도착할 수 있는 이동할 수 있는 경우의 수를 구하여라.
입력
첫 번째 줄에 정수 가 공백으로 구분되어 주어진다.
두 번째 줄부터 개의 줄에 걸쳐 각 줄에 폭탄의 위치 를 나타내는 가 공백으로 구분되어 주어진다.
폭탄의 위치는 시작점과 도착점을 제외한 정수 좌표에 있으며, 모두 다르다.
출력
성모가 이동할 수 있는 경우의 수를 출력하라. 답이 커질 수 있으므로 로 나눈 나머지를 출력한다. 단, 은 소수이다.
풀이
입시를 하는 대한민국 고등학생으로서 이런 조합론 문제는 너무 많이 보았다.
위 그림에서는 오른쪽 5번, 아래쪽 4번 총 9개의 화살표를 배열하는 경우의 수이므로
전체 경우의 수는 9C4.
거기서 폭탄을 지나가는 것을 빼주면 되는데, 이 경우의 수는 (폭탄까지 가는 경우의 수) 곱하기 (폭탄에서 종점까지 가는 경우의 수)
즉, 4C2 * 5C2이다.
전체 경우의 수에서 이걸 빼주면 된다.
단, 이 문제는 이 폭탄이 20개 있다.
즉, 포함 배제의 원리를 이용하여 세주어야 할 것이다.
아래 그림을 보자.
각 폭탄에 대하여 여사건을 해주면 될 것 같지만, 그러면 S-1-2-4-F와 같이 여러 폭탄을 지나는 경로가 겹쳐져서 세진다.
그러면
(전체 경로의 수) - (폭탄을 1개 지나는 경우의 수) + (폭탄을 2개 지나는 경우의 수) - (폭탄을 3개 지나는 경우의 수) .....
이걸 계산하겠다는 아이디어가 가장 먼저 떠오르는데.....이걸 20번씩이나 하겠다고? 귀찮다.
아이디어는 재귀함수를 이용하는 것이다.
관찰을 하자면, 현재 포인트가 x, y일때, 앞으로 지날 수 있는 폭탄의 좌표는 x, y보다 크거나 같다.
함수 sol(x, y)를 정의하자. x, y는 시작점의 좌표이다. 경로가 끝나는 지점은 무조건 N, M이다.
맨 처음에 폭탄 무시하고 x, y에서 N, M까지 갈 수 있는 경우를 조합으로 계산해준다.
그리고 x, y에서 갈 수 있는 모든 폭탄에 대해서(x좌표, y좌표를 비교해주면 된다. 굳이 정렬이 필요없는 풀이), 다음을 빼주면 된다.
(x, y에서 폭탄까지 가는 경로의 수) * sol(폭탄 좌표)
재귀함수 sol이 이런 포함배제 관계를 알아서 전부 해결해 줄 것이다(이 아이디어가 한번에 떠오른 나도 레전드).
약간 dp같기도 하고 안 같기도 한 느낌이 없지않게 있다.
그리고 한가지 주의할 점은, 수의 범위가 100만정도 되기때문에 python의 내장함수 math.comb를 쓰면 느리다.
미리 팩토리얼을 100만까지 계산해놓고 직접 모듈러 역원 연산을 하여 nCk를 구하는 것이 좋을 것이다.
(처음에는 뤼카 정리를 쓸까 했는데 쓰고 보니까 굳이 필요없음을 깨달았다)
그리고 코드 구현은 아래와 같고, 매우매우매우 간단하다.
그래서 딱히 숏코딩 작업을 안했는데도 바로 숏코딩 2등을 해버렸다.
P = 1_000_000_007
N, M, K = map(int, input().split())
fac = [1]
for i in range(1, N+M+1):
fac.append(fac[-1]*i%P)
bomb = []
for i in range(K):
x, y = map(int, input().split())
bomb.append((x, y))
def C(N, K):
son = fac[N]
mom = fac[K]*fac[N-K]%P
large = pow(mom, P-2, P)
return son*large%P
def sol(x, y):
ans = 0
ans += C(N-x+M-y, N-x)%P
for nx, ny in bomb:
if x <= nx and y <= ny and not (x == nx and y == ny):
ans -= C(nx-x+ny-y, nx-x)*sol(nx, ny)
ans%=P
return ans%P
print(sol(0, 0))
다만 위와 같이 구현하면
ans += C(N-x+M-y, N-x)%P
이부분때문에 숏코딩 하기가 힘들다. 항이 4개씩이나 있어서...
이를 해결하기 위해
저기의 N, M을 없애주는 아이디어를 떠올린다.
역으로 N, M에서 출발해서 0, 0이 도착점이 되게끔 코드를 다시 짜주는 것이다.
그러면 부등호 방향 몇 개 바꾸고, 몇 바이트 정도를 없앨 수 있다.
'PS' 카테고리의 다른 글
| [Python] 백준 14428 - 수열과 쿼리 16 (0) | 2025.05.17 |
|---|---|
| [Python] 백준 11437 - LCA (0) | 2025.05.16 |
| [Python] 백준 1150 - 백업 (0) | 2025.05.05 |
| [Python] 백준 14517 - 팰린드롬 개수 구하기 (Large) (0) | 2025.04.25 |
| [Python] 백준 10220 - Self Representing Seq (0) | 2025.04.22 |