10164번: 격자상의 경로

문제링크 - codeup

문제링크 - acmicpc

행의 수가 N$N$이고 열의 수가 M$M$인 격자의 각 칸 에 1부터 N×M$N\times M$까지의 번호가 첫 행부터 시작하 여 차례로 부여되어 있다. 격자의 어떤 칸은 O표시가 되어 있다. (단, 1$1$번 칸과 N×M$N\times M$번 칸은 O 표시가 되어 있지 않다. 또한, O 표시가 되어 있는 칸은 최대 한 개이다. 즉, O 표시가 된 칸 이 없을 수도 있다.)

행의 수가 3$3$이고 열의 수가 5$5$인 격자에서 각 칸 에 번호가 1$1$부터 차례대로 부여된 예가 아래에 있다. 이 격자에서는 8$8$번 칸에 O 표시가 되어 있다.

격자의 1$1$번 칸에서 출발한 어떤 로봇이 아래의 두 조건을 만족하면서 N×M$N\times M$번 칸으로 가고자 한다.

조건 1: 로봇은 한 번에 오른쪽에 인접한 칸 또는 아래에 인접한 칸으로만 이동할 수 있다. (즉, 대 각선 방향으로는 이동할 수 없다.)

조건 2: 격자에 O로 표시된 칸이 있는 경우엔 로 봇은 그 칸을 반드시 지나가야 한다.

위에서 보인 것과 같은 격자가 주어질 때, 로봇이 이동할 수 있는 서로 다른 경로의 두 가지 예가 아래에 있다.

1→2→3→8→9→10→15$1\to 2\to 3\to 8\to 9\to 10\to 15$

1→2→3→8→13→14→15$1\to 2\to 3\to 8\to 13\to 14\to 15$

격자에 관한 정보가 주어질 때 로봇이 앞에서 설 명한 두 조건을 만족하면서 이동할 수 있는 서로 다른 경로가 총 몇 개나 되는지 찾는 프로그램을 작성하라.

입력

입력의 첫째 줄 에는 격자의 행의 수와 열의 수를 나타내는 두 정 수 N$N$ 과 M(1≤N,M≤15)$M(1\le N,M\le 15)$, 그리고 O로 표시 된 칸의 번호를 나타내는 정수 K(K=0또는1<K<N×M)$K(K=0또는1<K<N\times M)$가 차례로 주어지며, 각 값은 공백으로 구분된다. K$K$의 값이 0$0$인 경우도 있는 데, 이는 O로 표시된 칸이 없음을 의미한다. N$N$과 M$M$이 동시에 1$1$인 경우는 없다.

출력

주어진 격자의 정보를 이용하여 설명한 조건을 만족하는 서로 다 른 경로의 수를 계산하여 출력해야 한다.

---

이번엔 acmicpc가 아닌 codeup이라는 사이트에서 문제를 풀었다.

물론 acmicpc에도 같은 문제가 있다.

이 문제는 시작이 가장 왼쪽 위이고, 마지막지점이 가장 오른쪽 아래이고,

이동은 오른쪽과 아래로밖에 할 수 없으므로 모든 경우는 최단경로일 것이다.

그런데 지점 K를 들러야 한다.

따라서 ((0,0)부터 K좌표 까지 경우의수) * (K좌표부터 (N-1,M-1)까지의 경우의수) 가 답이 될 것이다.

K가 0일경우는 (0,0)부터 (N-1,M-1)까지의 경우의 수를 출력하면 된다.

고등학교 2학년 과정 - 확률과 통계에서 배운 최단경로 경우의수 구하기

최단경로 = (가로길이+세로길이)! / ( (가로길이)! * (세로길이)! )

그런데 풀다가 문제가 생겼다.

Floating point exception:부동 소수점 에러,0으로 나누었는지 확인하세요.

...네?

30분동안 끙끙대다가 문제를 발견했다! 유레카

말 그대로 0으로 나눈것이 잘못. ( k좌표부터 끝점까지 뺄때 이 오류가 생긴다 )

또 수정했는데 또 안되더라 젠장 이유를 모르겠다

그래서 DP로 풀었다

소스링크