[BOJ 1577] 도로의 개수

https://www.acmicpc.net/problem/1577 1577번: 도로의 개수 문제 세준이가 살고 있는 도시는 신기하게 생겼다. 이 도시는 격자형태로 생겼고, 직사각형이다.

도시의 가로 크기는 N이고, 세로 크기는 M이다. 또, 세준이의 집은 (0, 0)에 있고, 세준이의 학교는 (N, M)에 있다.

따라서, 아래 그림과 같이 생겼다. 세준이는 집에서 학교로 가는 길의 경우의 수가 총 몇 개가 있는지 궁금해지기 시작했다.

세준이는 항상 최단거리로만 가기 때문에, 항상 도로를 정확하게 N + M개 거친다. 하지만, 최근 들어 이 도시의 도로가 부실공사 의혹으로 공사중인 곳이 있다.

도로가 공사 중일 때는, 이 ... www.acmicpc.net 공사 중인 도로가 없다고 생각하고 임시의 3 x 4의 목적지까지 가는 거리를 구해 봅시다. 각 시작점에서 첫 열과 첫 행은 당연히 가는 경우의 수가 1가지 밖에 없습니다.

이후 경우에 수를 구해보면 다음과 같이 나타나는 것을 볼 수...