장애물 피한 격자 경로
골드 III의견: 0
로봇이 좌표평면 격자의 출발점 \((0, 0)\) 에서 목적지 \((X, Y)\) 까지 이동한다. 한 번에 오른쪽(\(x\) 좌표를 \(1\) 증가) 또는 위쪽(\(y\) 좌표를 \(1\) 증가) 으로만 한 칸 이동할 수 있다.
그런데 좌표 \((P_1, Q_1)\) 과 \((P_2, Q_2)\) 두 곳에 장애물이 있어 그 칸들을 지날 수 없다. 두 장애물의 좌표는 서로 다르다(다만 출발점이나 목적지가 장애물일 수는 있다). \((0,0)\) 에서 \((X,Y)\) 까지 두 장애물을 모두 지나지 않고 가는 서로 다른 경로의 수를 구하여라.
경우의 수가 매우 클 수 있으므로 \(1\,000\,000\,007\) 로 나눈 나머지를 출력하여라.
- \(0 \le X, Y \le 200{,}000\)
- \(0 \le P_1, Q_1, P_2, Q_2 \le 200{,}000\)
- \((P_1, Q_1) \ne (P_2, Q_2)\)
첫 줄에 여섯 정수 \(X\), \(Y\), \(P_1\), \(Q_1\), \(P_2\), \(Q_2\) 가 공백으로 구분되어 주어진다.
\((P_1, Q_1)\) 과 \((P_2, Q_2)\) 는 서로 다른 좌표임이 보장된다.
장애물을 지나지 않는 경로의 수를 \(1\,000\,000\,007\) 로 나눈 나머지를 한 줄에 출력한다.
2 2 1 0 1 21\((0,0)\to(2,2)\) 전체 경로는 \(\binom{4}{2}=6\) 개이다. 장애물 \((1,0)\) 을 지나는 경로 \(3\) 개, \((1,2)\) 를 지나는 경로 \(3\) 개를 빼고, 두 장애물을 모두 지나는 경로 \(1\) 개를 포함-배제로 다시 더하면 \(6-3-3+1=1\) 이다. 두 장애물이 한 단조 경로 위에 있어 순서가 중요함을 보여준다. 답은 1 이다.
3 3 1 2 2 12전체 경로는 \(\binom{6}{3}=20\) 개이다. 두 장애물 \((1,2)\) 와 \((2,1)\) 은 한 단조 경로 위에 함께 놓일 수 없으므로(둘을 모두 지나는 경로가 없으므로), 각각을 지나는 경로 수만 빼면 된다. 답은 2 이다.
riseoj 작성
출처 Original
평가 및 의견
장애물 피한 격자 경로
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
장애물 피한 격자 경로