문제
n*m 격자에서 왼쪽 위(0,0)에서 오른쪽 아래(n,m)까지 갈 수 있는 길의 수를
헤아리고자 한다.
길을 갈 때 몇 가지 제약사항이 있다.
(1) 격자 위의 선을 따라간다.
(2) 아래쪽 또는 오른쪽으로만 갈 수 있다.
(3) (0,0)과 (n,m)을 잇는 대각선보다 위쪽에 있는 점들은 통과할 수 없다.
(대각선에 위치하는 점은 통과할 수 있다.)
아래의 그림에서 흰점은 통과할 수 없는 점이고 검은 점은 통과할 수 있는 점이다.
예를 들어, 3*4 격자에서 갈 수 있는 길은 다음과 같이 5가지가 있다.
격자의 크기가 입력되었을 때 (0,0)부터 (n,m)까지 갈 수 있는
길의 수를 출력하는 프로그램을 작성하시오.
입력
1. 두 개의 정수 n과 m이 입력된다.
2. n은 격자의 세로 크기를, m은 격자의 가로 크기를 각각 나타낸다
[입력값의 정의역]
1 <= n, m <= 100
출력
(0,0)에서 (n,m)까지 갈 수 있는 길의 수를 출력한다.
예제
3 4
5
출처
문제해결을 위한 창의적 알고리즘 (고급)
로그인해야 코드를 작성할 수 있어요.